并查集
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
| int f[N],w[N]; int n,m;
void init(){ for(int i=1;i<=n;i++){ f[i] = i; w[i] = 1; } }
int find(int u){ if(u == f[u]) return u; else return f[u] = find(f[u]); }
void join(int u,int v){ u = find(u); v = find(v); if(u == v) return; f[u] = v; w[v] += w[u]; }
bool isSame(int u,int v){ u = find(u); v = find(v); return u == v; }
|
求图是否连通
连通图
由于如果都连通时,所有点的跟都是一样的,因此以该根的图的节点个数会等于总节点个数。
1 2 3 4 5
| int fa = find(1); if(w[fa] == n) cout << "YES" << "\n"; else{ cout << "NO" << "\n"; }
|
求连通块个数
畅通工程
刚开始时所有节点的根都为本身,连通块个数为节点个数。
最后,计算有多少个节点的根不再为本身了,改变了一个连通块个数就减一
1 2 3 4 5 6
| int cnt = n; for(int i=1;i<=n;i++){ if(f[i] != i){ cnt --; } }
|