并查集

并查集是快速实现大量数据的合并和查找，时间复杂度为O(log₂n)

 

以下是两层并查集：(结点与自己的祖先直接相连)

1> 初始化 祖先赋为自己father[i=1~n] = i;

2> 并：若总根不同，将两个结点的总根合并：第一个总根做第二个总根的祖先

3> 查：查看father是否相同

#include <iostream> using namespace std; int n, m, q; //一共n个人，m对亲戚关系，q次查询 int father[10001]; int Find_f(int x) { //找总根 if(x == father[x]) return x; //说明x是总根 father[x] = Find_f(father[x]); return father[x]; } int Unite(int a, int b) { //合并 int f1 = Find_f(a); int f2 = Find_f(b); if(f1 == f2) return 0; //f1 = f2 已经是亲戚关系 father[f2] = f1; return 1; } int main() { int x, y, c, d; cin >> n >> m >> q; for(int i=1; i<=n; i++) father[i] = i; //初始化 for(int i=1; i<=m; i++) { cin >> x >> y; Unite(x, y); //x、y成为亲戚 } for(int i=1; i<=n; i++) Find_f(i); //上面Unite只是合并总根，总根下的子结点还没更新 for(int i=1; i<=q; i++) { cin >> c >> d; //查询c、d是不是亲戚 if(father[c] == father[d]) cout << "Yes" << endl; else cout << "No" << endl; } return 0; }