verify/yosupo/yosupo-unionfind.test.cpp

View this file on GitHub
Last update: 2023-01-08 14:16:34-05:00
Problem: https://judge.yosupo.jp/problem/unionfind

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/unionfind"

#include "../../library/contest/template-minimal.hpp"
#include "../../library/graphs/dsu.hpp"

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, q;
	cin >> n >> q;
	DSU dsu;
	dsu.init(n);
	while (q--) {
		int t, u, v;
		cin >> t >> u >> v;
		if (t == 0) {
			dsu.unite(u, v);
		} else {
			cout << dsu.same_set(u, v) << '\n';
		}
	}
	return 0;
}

#define PROBLEM "https://judge.yosupo.jp/problem/unionfind"


#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <iostream>
#include <iomanip>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

struct DSU {
  std::vector<int> e;

  DSU() = default;
  DSU(int n) { init(n); }

  void init(int n) { e = std::vector<int>(n, -1); }

  int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }

  bool same_set(int a, int b) { return get(a) == get(b); }

  int size(int x) { return -e[get(x)]; }

  bool unite(int x, int y) {
    x = get(x), y = get(y);
    if (x == y) return false;
    if (e[x] > e[y]) std::swap(x, y);
    e[x] += e[y];
    e[y] = x;
    return true;
  }
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, q;
	cin >> n >> q;
	DSU dsu;
	dsu.init(n);
	while (q--) {
		int t, u, v;
		cin >> t >> u >> v;
		if (t == 0) {
			dsu.unite(u, v);
		} else {
			cout << dsu.same_set(u, v) << '\n';
		}
	}
	return 0;
}