并查集总结

Void_Trailwalker · 2025-04-04 20:38:18 · 学习·文化课

什么是并查集

并查集其实是一个树林（很多棵树），最主要就只有查找和合并。

• 查找：查找一个节点的祖先，即一直求父亲节点直到自己是自己的父亲（及根节点）
• 合并：两个节点 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;