并查集是一种用于分离集合操作的抽象数据类型。它所处理的是“集合”之间的关系，即动态地维护和处理集合元素之间复杂的关系，当给出两个元素的一个无序对(a,b)时，需要快速“合并”a和b分别所在的集合，这其间需要反复“查找”某元素所在的集合。“并”、“查”和“集”三字由此而来。在这种数据类型中，n个不同的元素被分为若干组。每组是一个集合，这种集合叫做分离集合。并查集支持查找一个元素所属的集合以及两个元素各自所属的集合的合并。 并查集本身不具有结构，必须借助一定的数据结构以得到支持和实现。数据结构的选择是一个重要的环节，选择不同的数据结构可能会在查找和合并的操作效率上有很大的差别，但操作实现都比较简单高效。并查集的数据结构实现方法很多，数组实现、链表实现和树实现。一般用的比较多的是数组实现。 1）初始化： for (i = 1; i <= n; i++) father[i] = i; 因为每个元素属于单独的一个集合，所以每个元素以自己作为根结点。 2）寻找根结点编号并压缩路径： int find (int x) { if (father[x] != x) father[x] = find (father[x]); return father[x]; } （3）合并两个集合： void unionn(int x,int y) { x = find(x);y = find(y); father[y] = x; }（4）判断元素是否属于同一集合： bool judge(int x,int y) { x = find(x); y = find(y); if (x == y) return true; else return false; }
并查集比起前面的一堆算法还算是比较的简单，这次的作业题也已经发出来，随学随做。
