并查集的介绍

并查集主要涉及到两种操作，合并和查找。举例说明应用的场景：有一个朋友圈，朋友圈存在若干好友关系。如果两个人有直接或者间接好友关系，那么他们就在同一个朋友圈中。如果A是B的好友，而B和C是好友，那么A和C也是好友。因为朋友圈中会有新的朋友关系出现，这时候需要对当中某些人是否在同一朋友圈中进行查找和合并，这就是一个典型的合并－查找问题，既包含了合并操作，又包含了查找操作。

并查集的实现

(1)初始化操作，初始状态每个结点都是自己的根结点。

const int N = 10000;
int f[N];
for(int i = 1;i <= n;i++)
{f[i] = i;
}

(2)查找，即找x结点的根结点，如果x的根节点是它本身，则直接返回，否则递归的去找它的父结点。

int Find(int x)
{if(x == f[x]) //如果x就是根节点{return x;}return Find(f[x]); //f[x]是x的父结点,向上递归查找
}

(3)合并，已知x和y有关系，则将x和y合并到一个父结点之上，比如可以将y合并到x上，此时x就是y的父结点。

并查集的例题

题目选自:

洛谷p1551： 亲戚

题目背景

若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。

题目描述

规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。

输入格式

第一行：三个整数n,m,p，（n<=5000,m<=5000,p<=5000），分别表示有n个人，m个亲戚关系，询问p对亲戚关系。

以下m行：每行两个数Mi，Mj，1<=Mi，Mj<=N，表示Mi和Mj具有亲戚关系。

接下来p行：每行两个数Pi，Pj，询问Pi和Pj是否具有亲戚关系。

输出格式

P行，每行一个’Yes’或’No’。表示第i个询问的答案为“具有”或“不具有”亲戚关系。

输入输出样例
输入 #1
6 5 3
1 2
1 5
3 4
5 2
1 3
1 4
2 3
5 6
输出 #1
Yes
Yes
No

题解如下:

#include<iostream>
using namespace std;const int N = 10000;
int f[N];int Find(int x)
{if(x == f[x]) //如果x就是根节点{return x;}return Find(f[x]);
}void Union(int x,int y)
{x = Find(x);y = Find(y);if(x != y){f[y] = x;}
}int main()
{int n,m,p,x,y;cin>>n>>m>>p;for(int i=1;i<=n;i++){f[i] = i;}for(int i=0;i<m;i++){cin>>x>>y;Union(x,y);}for(int i=0;i<p;i++){cin>>x>>y;if(Find(x)==Find(y)){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}}return 0;
}