# **并查集** # ## **概述** ## 在计算机科学中，**并查集**是一种树型的数据结构，用于处理一些不交集的合并及查询问题。它的本质是将每一个集合以树表示的数据结构。 ## **操作** ## * ### **初始化** ### 并查集的初始化是将最初的n个元素划分成n个集合，即它们各自的父亲即为他们自己，他们各自的深度都为1。 ``` void init(){ for(int i=1;i<=n;i++) par[i]=i,ran[i]=1; } ``` * ### **查询根节点** 我们知道，由于每一个集合都是一棵树，因此每个集合的代表元素也就是这个元素所在集合构成的树的根节点。如果我们想得知某个元素的所属集合，就需要找到根节点。 最朴素的寻找根节点的方法就是沿着路径一直往上走，但是如果这个集合树退化成为一条链的话，那么单次查询根节点的复杂度就变为了O(n)。那么我们怎么来进行优化呢？优化的方法就是路径压缩:即找到节点x的根节点之后顺便把它的子孙也加到它的后面。这样操作的速度就会快很多。 ``` int find(int x){ return x==par[x]?x:find(par[x]); } ``` * ### **合并两个集合** 合并两个元素x和y所在的集合就要先找到各自的根节点，如果根节点相等，说明此时两个元素已经在一个集合当中，否则我们就按照他们根节点的深度（秩）来进行合并，深度（秩）小的总是指向最大的，话句话说，总是将比较矮的作为子树，添加到较高的树中。 ``` void unite(int a,int b){ a=find(a); b=find(b); if(a==b) return ; if(ran[x]>ran[y]) par[y]=x; else{ par[x]=y; if(ran[x]==ran[y]) ran[y]++; } } ``` * ## **求解集合个数** 当我们构造好了一个并查集后，如何来求当前的集合个数呢？我们只需要遍历每个元素，对于元素i，如果par[i]=i，那么就说明i是一个集合的代表，计数加一即可。这个方法可以被用来判断所求的最小生成树是否联通。 ## **例题** ## ### [The Suspects](http://poj.org/problem?id=1611) 对于输入的序号都加1，将每组的元素进行合并操作，求出1所在集合的大小即可。 ``` #include<iostream> #include<cstdio> #include<string.h> using namespace std; const int N = 1e6+10; int num[N],ran[N],par[N]; int n; void init(){ for(int i=1;i<=n;i++){ par[i]=i,ran[i]=1,num[i]=1; } } int find(int x){ return x==par[x]?x:find(par[x]); } void unite(int x,int y){ x=find(x); y=find(y); if(x==y) return ; if(ran[x]>ran[y]){ par[y]=x; num[x]+=num[y]; //合并之后集合大小也相加。 } else{ par[x]=y; num[y]+=num[x]; if(ran[x]==ran[y]) ran[y]++; } } int main(){ int m; while(scanf("%d %d",&n,&m)&&(n+m)){ init();int x,y,k; for(int i=1;i<=m;i++){ scanf("%d",&k); scanf("%d",&x);k--; x++; while(k--){ scanf("%d",&y); y++; unite(x,y); } } printf("%d\n",num[find(1)]); } return 0; } ```