test/unionfind.test.cpp
Depends on
Code
#define PROBLEM "https://judge.yosupo.jp/problem/unionfind"
#include "../data_structures/unionfind.cpp"
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, q;
cin >> n >> q;
UnionFind uf(n);
for (int i = 0; i < q; i++) {
int t, u, v;
cin >> t >> u >> v;
if (t == 0)
uf.unite(u, v);
else if (uf.same(u, v)) {
cout << 1 << '\n';
} else {
cout << 0 << '\n';
}
}
}
#line 1 "test/unionfind.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/unionfind"
#line 2 "data_structures/unionfind.cpp"
#include <bits/stdc++.h>
using namespace std;
// UnionFind
// グループを管理するデータ構造
struct UnionFind {
int n;
vector<int> parents;
UnionFind(int n) : n(n) {
parents.assign(n, -1);
}
// find
// xの親を返す.
// 制約: 0 <= x < n
int find(int x) {
if (parents[x] < 0) return x;
return parents[x] = find(parents[x]);
}
// unite
// xとyを含むグループを併合
// 制約: 0 <= x,y < n
void unite(int x, int y) { // xとyの含むグループを併合
int px = find(x);
int py = find(y);
if (parents[px] > parents[py]) swap(px, py);
if (px != py) {
parents[px] += parents[py];
parents[py] = px;
}
}
// same
// xとyが同じグループにいるか判定
// 制約: 0 <= x,y < n
bool same(int x, int y) {
return find(x) == find(y);
}
// size
// xと同じグループのメンバーの個数
// 制約: 0 <= x < n
int size(int x) {
return -parents[find(x)];
}
// root
// 根を全て列挙する
vector<int> root() {
vector<int> res;
for (int i = 0; i < n; i++) {
if (parents[i] < 0) res.push_back(i);
}
return res;
}
// group_count
// グループの数を返す.
int group_count() { // ufのグループの数を数える
return (int)root().size();
}
};
#line 5 "test/unionfind.test.cpp"
using namespace std;
int main() {
int n, q;
cin >> n >> q;
UnionFind uf(n);
for (int i = 0; i < q; i++) {
int t, u, v;
cin >> t >> u >> v;
if (t == 0)
uf.unite(u, v);
else if (uf.same(u, v)) {
cout << 1 << '\n';
} else {
cout << 0 << '\n';
}
}
}
Back to top page