洛谷P1551——亲戚（并查集入门）

题目传送门

1.并查集是什么？

本质是一种树形结构（拥有相同根节点的多叉树），可以很方便的判断集合元素之间的从属关系。

2.如何维护好一个并查集？

并查集的本质在于相同的根节点，那么只需要通过某种方式记录好组内每一个元素的根节点，比较两个元素根节点是否相同就可以判断是否在同一个集合内。

3.如何判断根节点？

我们可以定义根节点的上一个节点为自己，这样子我们便有一个判断的条件了。

开始写代码吧。

头部分

#include<iostream> using namespace std; int fa[5010]; int main{ int a,b,c; cin>>a>>b>>c; int m,n; }

首先我们要初始化所有数的根为自身

for(int i=1;i<=a;i++){ fa[i]=i;//fa是father数组，记录其上一个节点信息 }

其次就是处理输入信息

我们要先读取两个整数，这两个整数是在同一个集合内的。

然后我们就要找他的根。

int find(int x){ while(x!=fa[x]){//循环找根节点（由根节点的定义 x=fa[x]; } return x;//返回找到的根节点 }

然后我们要统一两个数的根，这里我们可以想象一个图

a d

b b b e e e e e e e e e e e e

c c c c c c.

虽然有点丑，但是应该能看到这是一个三层和两层的树，我们要做的实际上是把他的根节点统一，即下图（如果这么丑也能算图的话）：

a

b b b d

c c c c c c. e e e e e e e e e e e e

其实就是把一棵树全部（注意是全部）嫁接到另一棵树上。

for(int i=0;i<b;i++){ cin>>m>>n; if(find(m)!=find(n)) fa[find(m)]=find(n);//将一棵树的根节点插入到另一棵树上 }

然后就是判断是否相同了，很简单，直接贴完整代码了

#include<iostream> using namespace std; int fa[5010]; int find(int x){ while(x!=fa[x]){ x=fa[x]; } return x; } int main(){ int a,b,c; cin>>a>>b>>c; int m,n; for(int i=1;i<=a;i++){ fa[i]=i; } for(int i=0;i<b;i++){ cin>>m>>n; if(find(m)!=find(n)) fa[find(m)]=find(n); } for(int i=0;i<c;i++){ cin>>m>>n; if(find(m)==find(n)) printf("Yes\n"); else printf("No\n"); } return 0; }