并查集模板

并查集有什么用

用于判断连通性——组成联通块族系问题

代码

// c++ #include <iostream> #define ll long long using namespace std; int father[5010]; // 构造 void initial(int n) { for(int i=0; i <= n; i++) father[i] = i; } // 查找 int find(int x) { return x == father[x] ? x : father[x] = find(father[x]); } // 相同吗 bool isSame(int x, int y) { return find(x) == find(y); } // 变成同一类 void my_union(int x, int y) { x = find(x); y = find(y); father[x] = y; return; } int main() { int n, m, p; cin >> n >> m >> p; initial(n); for(int i=0; i<m; i++) { int j, k; cin >> j >> k; my_union(j, k); } for(int i=0; i<p; i++) { int j, k; cin >> j >> k; cout<< (isSame(j,k) ? "Yes":"No") << endl; } return 0; } // java class UF { // Number of connected branches private int count; // save the tree private int[] parent; // save the weight of thr node private int[] size; public UF(int size) { this,count = size; parent = new int[size]; this.size = size; for (int i = 0; i < size(); i++) { parent[i] = i; size[i] = 1; } } // union public void union(int p, int q) { int rootP = find(p); int rootQ = find(q); if (rootP == rootQ) return; // to be balanced, small to big if (size[rootP] > size[rootQ]) { parent[rootQ] = rootP; size[rootP] += size[rootQ]; } else { parent[rootP] = rootQ; size[rootQ] += size[rootP]; } count--; } // connected public boolean connected(int p, int q) { return find(p) == find(q); } // find ---o(1) public int find(int t) { while (parent[t] != t) { parent[t] = parent[parent[t]]; t = parent[t]; } } }