并查集总结
什么是并查集
并查集其实是一个树林(很多棵树),最主要就只有查找和合并。
- 查找:查找一个节点的祖先,即一直求父亲节点直到自己是自己的父亲(及根节点)
- 合并:两个节点
x 和y ,查找它们的祖先,将x 的祖先指向y 的祖先 - 路径压缩:查找的常用技巧,将该节点指向它的祖先,这样下次查找就可以很快了
例题一:P2814
其实就是姓名的处理麻烦了些,还是可以当作模板题的。
if(tmp=="$")break; else if(tmp[0]=='#'){ string name = tmp.substr(1,tmp.size()); if(find(name)=="")a[name] = name; while(1){ cin >> tmp; if(tmp[0]=='?'||tmp[0]=='#')break; string name2 = tmp.substr(1,tmp.size()); a[name2] = name; } } string n = tmp.substr(1,tmp.size()); if(tmp[0]=='?')cout << tmp.substr(1,tmp.size()) << " " << find(n) << endl; else if(tmp[0]=='#')continue; cin >> tmp;例题二:P1536
这道题其实就是求树的数量,也就是根节点的数量。因为在并查集中根节点的父亲等于自身,可以利用这个性质O(N)地求出数量。或者每有一条边将两棵树连起来,根节点数量减一(初始为
n )cin >> n;if(n==0)break; cin >> m; for(int i=1;i<=n;i++)a[i] = i; for(int i=1;i<=m;i++){ int a1 , b;cin >> a1 >> b; int f = find(a1) , g = find(b); if(f!=g)a[f] = g; } int ans = 0; for(int i=1;i<=n;i++)if(a[i]==i)ans++; cout << ans - 1 << endl;接下来上点难度!组合算法:二分+bfs+并查集
例题三:P2658
看出这是二分很简单,bfs也不难,但是怎么想到要用并查集呢?你写的时候会发现一个问题:怎么判断路标是否连通?这时并查集就要上场了。将所有联通的点连起来,再判断所有路标的祖先是否相同。
for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++)b[i*1000+j] = i * 1000 + j , fl[i][j] = 0; } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ for(int k=0;k<4;k++){ if(i+dx[k]>n||i+dx[k]<=0||j+dy[k]>m||j+dy[k]<=0){ continue; } if(abs(a[i][j]-a[i+dx[k]][j+dy[k]])<=x){ int fx = find(b[i*1000+j]); int fy = find(b[(i+dx[k])*1000+j+dy[k]]); if(fx!=fy)b[fx] = fy; } } } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(f[i][j]&&find(b[sx*1000+sy])!=find(b[i*1000+j])){ return 0; } } } return 1;