题目描述
输入格式
第一行: 三个整数 n,m,p,(n<=5000,m<=5000,p<=5000), 分别表示有 n 个人, m 个亲戚关系, 询问 p 对亲戚关系.
以下 m 行: 每行两个数 Mi,Mj,1<=Mi,Mj<=N, 表示 Ai 和 Bi 具有亲戚关系.
输出格式
P 行, 每行一个'Yes'或'No'. 表示第 i 个询问的答案为 "具有" 或 "不具有" 亲戚关系.
样例输入:
- 6 5 3
- 1 2
- 1 5
- 3 4
- 5 2
- 1 3
- 1 4
- 2 3
- 5 6
样例输出:
Yes
Yes
No
解题思路: 先进行初始化每个元素的祖宗节点为 - 1, 然后根据亲戚关系进行合并, 查找祖先节点的时候要注意终止条件, 这里的终止条件为 - 1.
- // 并查集
- //1. 初始化
- //2. 查找
- //3. 合并
- #include<iostream>
- using namespace std;
- int n,m,p;
- int pre[5050];
- // 初始化
- void init()
- {
- for(int i = 1; i <= n; i++){
- pre[i] = -1; //pre[i] 代表 i 的父节点
- }
- }
- // 查找集合 i 的源头 (递归实现)
- int find(int i){
- if(pre[i] == -1) // 如果集合 i 的父亲是 - 1, 说明自己就是源头, 返回自己 (一颗树向上回溯查找, 直到源头)
- return i;
- return find(pre[i]);
- }
- void gets(int a,int b){
- int x = find(a); // 查找 a 的源头
- int y = find(b);
- if(x != y){ // 如果 a 和 b 的源头不相同, 则合并
- pre[y] = x;
- }
- }
- int main(){
- cin>>n>>m>>p;
- init();
- int a,b;
- for(int i = 1; i <= m; i++){
- cin>>a>>b;
- gets(a,b);
- }
- for(int i = 1; i <= p; i++){
- cin>>a>>b;
- if(find(a) != find(b)){
- cout<<"No"<<endl;
- }
- else
- cout<<"Yes"<<endl;
- }
- return 0;
- }
并查集
来源: http://www.bubuko.com/infodetail-3498874.html