丽水市莲都区建设局网站,三站合一网站建设,吕梁市建设局网站,西宁市解封最新消息文章目录一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解三、知识风暴并查集一、题目
1、原题链接 1249. 亲戚 2、题目描述 或许你并不知道#xff0c;你的某个朋友是你的亲戚。 他可能是你的曾祖父的外公的女婿的外甥女的表姐的孙子。 如果…
文章目录一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解三、知识风暴并查集一、题目
1、原题链接 1249. 亲戚 2、题目描述 或许你并不知道你的某个朋友是你的亲戚。 他可能是你的曾祖父的外公的女婿的外甥女的表姐的孙子。 如果能得到完整的家谱判断两个人是否是亲戚应该是可行的但如果两个人的最近公共祖先与他们相隔好几代使得家谱十分庞大那么检验亲戚关系实非人力所能及。 在这种情况下最好的帮手就是计算机。 为了将问题简化你将得到一些亲戚关系的信息如Marry和Tom是亲戚Tom和Ben是亲戚等等。 从这些信息中你可以推出Marry和Ben是亲戚。 请写一个程序对于我们的关于亲戚关系的提问以最快的速度给出答案。 输入格式 输入由两部分组成。 第一部分以 N,M 开始。N 为问题涉及的人的个数。这些人的编号为 1,2,3,…,N。下面有 M 行每行有两个数 ai,bi表示已知 ai 和 bi 是亲戚。 第二部分以 Q 开始。以下 Q 行有 Q 个询问每行为 ci,di 表示询问 ci 和 di 是否为亲戚。 输出格式 对于每个询问 ci,di输出一行若 ci 和 di 为亲戚则输出Yes否则输出No。 数据范围 1≤N≤20000,1≤M≤106,1≤Q≤106 输入样例 10 7
2 4
5 7
1 3
8 9
1 2
5 6
2 3
3
3 4
7 10
8 9输出样例 Yes
No
Yes二、解题报告
1、思路分析
1利用并查集将所有互为亲戚的合并为同一个集合。 2通过查找两个结点的祖宗结点是否相同来判断两人是否为亲戚。 3并查集模板题注意细节并且此题使用cin、cout会超时应使用scanf、printf或puts进行输入输出。
2、时间复杂度
时间复杂度为O(n)
3、代码详解
#include iostream
using namespace std;
const int N20010;
int n,m;
int p[N]; //p[]存储每个结点的祖宗结点
//查找操作返回x的祖宗结点
int find(int x){if(p[x]!x) p[x]find(p[x]); //如果p[x]不是祖宗的话递归查找x的祖宗return p[x]; //直到找到x的祖宗返回
}
int main(){scanf(%d%d,n,m); //使用cin、cout会TLE//初始化每个结点的祖宗为自身for(int i1;in;i){p[i]i;}while(m--){int a,b;scanf(%d%d,a,b);if(find(a)find(b)) continue;p[find(b)]find(a); //a,b的祖宗结点不同则合并}int q;cinq;while(q--){int c,d;scanf(%d%d,c,d);if(find(c)find(d)) puts(Yes); //祖宗相同输出Yes否则输出Noelse puts(No);}return 0;
}三、知识风暴 并查集 并查集主要用于处理一些不相交集合的合并问题。具体操作可以参考我的这篇博客点击这里的“知识风暴”模块。
