并查集:并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。
算法：用集合中的某个元素来代表这个集合，该元素称为集合的代表元。一个集合内的所有元素组织成以代表元为根的树
形结构。对于每一个元素 parent[x]指向x在树形结构上的父亲节点。如果x是根节点，则令parent[x] = x。对于查找操
作，假设需要确定x所在的的集合，也就是确定集合的代表元。可以沿着parent[x]不断在树形结构中向上移动，直到到达
根节点。判断两个元素是否属于同一集合，只需要看他们的代表元是否相同即可。
算法优化:路径压缩
为了加快查找速度，查找时将x到根节点路径上的所有点的parent设为根节点，该优化方法称为压缩路径。
用途
1、维护无向图的连通性。支持判断两个点是否在同一连通块内，和判断增加一条边是否会产生环。（不理解）
2、用在求解最小生成树的Kruskal算法里。
题目:
#include<iostream> #include<vector> #include<algorithm> #include<string> #include<set> #include<stdio.h> using namespace std; #define maxLen class disjointSets{ public: int N;//节点数 int pre[maxLen + 1]; //下标从1开始 set<int> rootSet; void initial(int _N){ N = _N; for (int i = 1; i <= N; ++i){ pre[i] = i; } } int find(int cur){ //查找根节点 int root = cur; while (pre[cur] != cur){ cur = pre[cur]; } int i = cur; int j; while (i != root){ //路径压缩,将节点i之上的所有节点的父节点都变为root j = pre[i]; pre[i] = root; i = j; } return root; } void join(int x,int y){ //判断 int rootX = find(x); int rootY = find(y); if (rootX != rootY){ pre[rootX] = rootY; } } void calRoot(){ rootSet.clear(); for (int i = 1; i <= N; ++i){ int root = find(i); rootSet.insert(root); } cout << rootSet.size()-1;//需要修建的桥的数目刚好是连通分量的数目减1; } }; int main(){ int N, M; disjointSets disSet; while (true) { cin >> N; if (N != 0){ disSet.initial(N); cin >> M; for (int i = 0; i < M; ++i){ int x, y; cin >> x >> y; disSet.join(x, y); } disSet.calRoot(); } else{ break; } } return 0; }
原文：http://www.cnblogs.com/codeDog123/p/6670744.html