并查集

含义：以下有几个含有若干数的集合，每一集合内的数相互关联，若两个集合中有相同的元素，那么这两个集合相关联，给两个数，问是否相关联

{1，2，3，4}

{5，6，7}

{1，3}

{6，8，9，10}

则1，3在一个大集合内，2，4在另一个大集合内。

用并查集

模板

预处理：将自己指向自己

1 int init(int n)
2 {
3 for(int i=0;i<n;i++)
4 pre[i]=i;
5 }

根节点的查找

1 int find_pre(int x)
2 {
3 if(pre[x]==x) return x;
4 return find_pre(pre[x]);
5 }

把两个根节点连在一起

1 int conect(int x,int y)
2 {
3 int x1=find_pre(x);
4 int y1=find_pre(y);
5 if(x1!=y1) return pre[x1]=y1; 
6 }

看两个点是否联通

1 int find_same(int x,int y)
2 {
3 int a=find_pre(x);
4 int b=find_pre(y);
5 if(a==b) return 1;
6 return 0;
7 }