test/yosupo/unionfind.test.cpp

View this file on GitHub
Last update: 2020-09-23 00:24:59+09:00
Problem: https://judge.yosupo.jp/problem/unionfind

Depends on

UnionFind (data-structure/UnionFind.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/unionfind"
#include <bits/stdc++.h>
#include "../../data-structure/UnionFind.hpp"

#define REP(a,b) for(int a=0;a<(int)(b);++a)

signed main(){
  int n, q;
  std::cin >> n >> q;

  UnionFind uf(n);
  REP(i, q) {
    int t, u, v;
    std::cin >> t >> u >> v;
    /* */if (t == 0) uf.unite(u, v);
    else if (t == 1) std::cout << uf.same(u, v) << "\n";
  }

  return 0;
}

#line 1 "test/yosupo/unionfind.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/unionfind"
#include <bits/stdc++.h>
#line 1 "data-structure/UnionFind.hpp"
// @brief UnionFind
// @shortcut UnionFind
// @description 素集合データ構造． union by size+path halvingの実装．O(α(N)).
// @docs data-structure/UnionFind.md
class UnionFind {
private:
	std::vector<int> par;
	std::vector<int> siz;

public:
	UnionFind(int sz_) : par(sz_), siz(sz_, 1) {
		for (int i = 0; i < sz_; ++i) par[i] = i;
	}
	void init(int sz_) {
		par.resize(sz_);
		siz.resize(sz_, 1);
		for (int i = 0; i < sz_; ++i) par[i] = i;
	}
	int find(int x) {
		while (par[x] != x) x = par[x] = par[par[x]];
		return x;
	}
	void unite(int x, int y) {
		x = find(x);
		y = find(y);
		if (x == y) return;
		if (siz[x] < siz[y]) std::swap(x, y);
		siz[x] += siz[y];
		par[y] = x;
	}
	bool same(int x, int y) {
		return find(x) == find(y);
	}
	int size(int x) {
		return siz[find(x)];
	}
};
#line 4 "test/yosupo/unionfind.test.cpp"

#define REP(a,b) for(int a=0;a<(int)(b);++a)

signed main(){
  int n, q;
  std::cin >> n >> q;

  UnionFind uf(n);
  REP(i, q) {
    int t, u, v;
    std::cin >> t >> u >> v;
    /* */if (t == 0) uf.unite(u, v);
    else if (t == 1) std::cout << uf.same(u, v) << "\n";
  }

  return 0;
}