1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
| int par[MAX_N]; int rank[MAX_N];
void init(int n) { for (int i = 0; i < n; i++) { par[i] = i; rank[i] = 0; } }
int find(int x) { if (par[x] = x) { return x; } else { return par[x] = find(par[x]); } }
void unite(int x, int y) { x = find(x); y = find(y); if (x == y)return; if (rank[x] < rank[y]) { par[x] = y; } else { par[y] = x; if (rank[x] == rank[y])rank[x]++; } }
bool same(int x, int y) { return find(x) == find(y); }
|