并查集学习笔记

并查集（union-find set）是一抽象数据类型。它所处理的是“集合”之间的关系，即动态地维护和处理集合元素之间复杂的关系，
当给出两个元素的一个无序对 (a,b) 时，需要快速“合并”a 和 b 分别所在的集合，这其间需要反复“查找”某元素所在的集合。“并”、“查”和“集”三字由此而来。

合并元素所在集合、查找元素所在集合

数组实现

并查集支持的操作

MAKE(x)：建立一个新的集合，其仅有的成员（同时就是代表）是 x。由于各集合是分离的，要求 x 没有在其它集合中出现过。
UNIONN(x,y)：将包含 x 和 y 的动态集合（例如 Sx 和 Sy）合并为一个新的集合，假定在此操作前这两个集合是分离的。结果的集合代表是 Sx∪Sy 的某个成员。一般来说，在不同的实现中通常都以 Sx 或者 Sy 的代表作为新集合的代表。此后，由新的集合 S 代替了原来的 Sx 和 Sy。
FIND(x)：返回一个指向包含 x 的集合的代表。

查找

int find(int x) {  // 用非递归的实现  
  while (father[x] != x) x = father[x];  
  return x;
  
}

int find(int x){// 用递归的实现  
    if (father[x] != x){return find(father[x]);  
    } else{return x;}   
}

合并

void unionn(int r1,int r2){father[r2] = r1;
  }

    int main(){
      cin >> n >> m;
      for (i = 1; i <= n; i++)
          father[i] = i;           // 建立新的集合，其仅有的成员是 i
      for (i = 1; i <= m; i++) {scanf("%d%d",&x,&y);
          int r1 = find(x);
          int r2 = find(y);
          if (r1 != r2){unionn(r1,r2);
            }   
      }    
      cin >> q;
      for (i = 1; i <= q; i++)  {scanf("%d%d",&x,&y);
          if (find(x) == find(y)){printf("Yes\n");
            } else {printf("No\n");
            }
      }
      return 0;
  }

本文由博客一文多发平台 OpenWrite 发布！