并查集

　　并查集，实现将本来不相交的集合合并，并进行查找。并查集归根结底还是树，实际上就是将森林合并成树的过程，通过合并的时候，各个节点能最终找到相同的祖宗，那么判断是否在一个集合中时，只需要比较是否是一个祖宗就好了。

 1 #include<cstdio>
 2 int father[100];
 3 void init()
 4 {
 5     for(int i=0;i<100;i++)
 6         father[i]=i;
 7 }
 8 int getfather(int x)
 9 {
10     if(x!=father[x])
11       father[x]=getfather(father[x]);
12     return father[x];
13 }
14 void m_Union(int x,int y)
15 {
16     x = getfather(x);
17     y = getfather(y);
18     if(x!=y)
19         father[x]=y;
20 }
21 int isSame(int x,int y)
22 {
23     return getfather(x)==getfather(y);
24 }
25 int main()
26 {
27     int k,a,b;
28     scanf("%d",&k);
29     init();
30     for(int i=0;i<k;i++)
31     {
32         scanf("%d%d",&a,&b);
33         m_Union(a,b);
34     }
35     scanf("%d%d",&a,&b);
36     if(isSame(a,b))
37         printf("YES
");
38     else
39         printf("NO
");
40     return 0;
41 }

　　开始要将各个节点的父节点指向自己，即初始时，节点是分开的，目前是森林状态。

　　将两个集合合并（mUnion函数）时，需要比较两个节点的祖宗是否相同，若相同，则说明两个节点在同一个集合中。

　　然后最后就是递归修改father数组，并找到最终的father节点。

　　举个栗子。

　　比如，1、2、3、4、5、6六个节点，初始时father[1]=1,father[2]=2......

　　1和2合并了，father[1]=2，2和3合并，father[2]=3，此时，1、2、3在一个集合中，但是father[1]=2不等于father[2]，所以，合并2和3时，先要x=father[2]=2,y=father[3]=3，不相等，father[2]=3。

　　此时有，father[1]=2,father[2]=3,father[3]=3

　　当调用getfather函数的时候，就会递归修改father数组，当我们查看1和3是否在一个集合中时，1和father[1]不想等，说明1已经被加入到一个另一个集合中，加入哪个集合中呢，集合是用集合元素标识的，所以，这若干集合，总有一个集合的父节点值就是该集合的标识，我们记它为F，所以我们只要找到它就可以了。所以1肯定属于某个F，所以我们就向上倒，没倒一次，就跟新一下父节点的值，因为，其父节点也是处于F中，最终我们找到了F，也就修改完了所有节点的father数组。

　　再复杂一点，1的父节点是2，2的父节点是3，3的父节点是4，4的父节点是4（我所说的标识F的节点），所以，当我们看1和4的时候，1能找到4，4能找到4，相等，就是存在于同一个集合中。

　　合并和查找都将修改father数组，但是这并不修改他们落在同一个F中的事实，事实上，只是F在变。