并查集适合维护具有非常强烈的传递性质，或者具有连通集合性质。
传递性质
具有传递效应的性质，比如A传递给B一个性质或者条件，让B同样拥有这个性质或者条件，这就是传递性。
连通集合性质
连通集合性，和数学概念上的的集合定义类似，比如A和B同属于一个集合，B和C同属于一个集合，那么A,B,C属于同一个集合。
初始化操作：
每个子对象的父节点初始化为自己
合并：
合并不同的集合
查找
判断两个子对象是否在同一个集合中
路径压缩
每一个集合可能包括了很多对象，有些对象可能存在一条很长的关系线，这时候把该集合所有对象的父节点转化为该集合的父节点，这就是路径压缩。
#include<iostream> using namespace std; int pre[1005];//每个点的前导点 int route[2005][2]; //可以配对的路线 int sum = 0; //符合条件的 即关键点的数量 //查找 int find(int x) { int r = x; while (pre[r] != r) r = pre[r]; int i = x, j; while (i != r)//路径压缩算法 { j = pre[i];//在改变他的前导点时，存储他的值 pre[i] = r; i = j;//改变他的前导点为根节点 } return r; }//
递归方法：
/*int find(int k)
{
if(f[k]==k)
return k;
return f[k]=find(f[k]);
}*/
void join(int x, int y) //组合 { int fx = find(x), fy = find(y);//分别记录x,y的根节点 if (fx != fy)//如果他们的根节点相同，则说明他们不是连通图 pre[fx] = fy;//将x的根结点 同 相连接 } int main() { int n, m; cin >> n>>m;//n表示站点的个数，m表示链路的个数 for (int i = 0; i < m; i++) { cin >> route[i][0] >> route[i][1]; join(route[i][0], route[i][1]);//将数据相互连接 } int q1,q2;//待询问的两个点 cin >> q1 >> q2; for (int ii = 0; ii < n; ii++)pre[ii] = ii; for (int j = 0; j < m; j++) { join(route[j][0], route[j][1]); } int a = find(q1); int b = find(q2); //如果边全部存在时不可达，则输出 -1； if (a != b) { cout << "-1" << endl; } else { for (int i = 1; i <= n; i++) //枚举每一个点 { if (i == q1 || i == q2)continue; //如果是被询问的点，跳过，无需遍历 此处是最关键的部分 for (int j = 1; j <= n; j++)pre[j] = j; //将每一个初始化 for (int j = 0; j < m; j++) { if (route[j][0] == i || route[j][1]==i)continue; //去除当前点互相关联的边 解决问题的关键 int a = find(route[j][0]); int b = find(route[j][1]); if (a > b) { a ^= b; b ^= a; a ^= b; };//交换 if (a != b)pre[b] = a; //以较小的点作为父节点 } int a = find(q1); int b = find(q2); if (a != b)sum++; } cout<<sum<<endl; } return 0; }