【超易懂】并查集

一、适用的问题描述：

某家族人口过于庞大，要判断两个是否是亲戚不容易。先给出已知的亲戚关系图，求任意给出的两人是否为亲戚关系。规定亲戚有传递性。

样例输入/输出：

6 5 3 （说明：6个人，5个亲戚关系，3组判断）1 2
1 5
3 4
5 2
1 31 4 Yes
2 3 Yes
5 6 No

二、并查集图文解释：

基础知识可参考：

http://wenku.baidu.com/link?url=GdU6OI4eoEOOk9UvEYvsy9enrCNwILxFxBVOjblSrk_dCG6nThAmrooh_saGYRGZywzNCpq08iMdAmvp8WG5bV6zCyGu_lG0lLpjnpNYS1W

三、下面的程序，和上图原理稍有不同。不是用最小元素标记，请读者仔细揣摩。

参考程序（C++版）

#define _CRT_SECURE_NO_DEPRECATE  //一定要放最前面才可起作用
#include  //可用cstdio代替
#define MAX 5001 //元素个数
int P[MAX]; //标记数组
using namespace std; //命名空间class MyClass{ //类声明public:MyClass(int N);//构造函数void merge(int p, int q);//加入关系圈bool isConnected(int p, int q);//判断是否在同一个圈中int count();//计算有多少个圈//int find(int p);private:int n;//数据成员};//如两值根的指向一致，则为同一圈bool MyClass::isConnected(int p, int q){if (P[p] == P[q]) return true; else return false;}//void MyClass::merge(int p, int q){int p_id = P[p];int q_id = P[q];if (!this->isConnected(p,q)){  //通过之前关系判断亲缘int i; for (i = 1; i < this->n; i++){if (P[i] == p_id) P[i] = q_id;  //右值链到左值上，他们有同一根}}}MyClass::MyClass(int N){this->n = N;int i;for (i = 1; i < N; ++i) P[i] = i;}int main(){int n, m, p, i, Mi, Mj;scanf("%d%d%d",&n,&m,&p);MyClass mc(n);for (i = 0; i < m; i++){scanf("%d%d", &Mi,&Mj);mc.merge(Mi,Mj);}for (i = 0; i < p; ++i){scanf("%d%d",&Mi,&Mj);if (mc.isConnected(Mi, Mj)) printf("Yes");else printf("No");}}

欢迎继续交流，兰理工Q：316190672

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！