并查集（图论）
📝 题目：亲戚 (洛谷 P1551)
题目背景
若某个家族人员过于庞大，要判断两个人是否是亲戚，确实不容易。
规定：$x$ 和 $y$ 是亲戚，$y$ 和 $z$ 是亲戚，那么 $x$ 和 $z$ 也是亲戚。也就是亲戚关系具有传递性。
题目描述
给你 $n$ 个人（编号从 1 到 $n$），$m$ 对亲戚关系，以及 $p$ 个亲戚关系询问。
输入格式
第一行：三个整数 $n, m, p$。（$n,m,p \le 5000$）
接下来 $m$ 行：每行两个整数 $M_i, M_j$，表示 $M_i$ 和 $M_j$ 具有亲戚关系。
接下来 $p$ 行：每行两个整数 $P_i, P_j$，询问 $P_i$ 和 $P_j$ 是否具有亲戚关系。
输出格式
一共输出 $p$ 行，每行一个Yes或No。表示对于每一个询问的答案。
输入输出样例
输入样例#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<bits/stdc++.h> using namespace std; #define N 5005 // int fa[N] = {0}; int find(int x){ if(fa[x] == x){ return x; } else{ fa[x] = find(fa[x]); return fa[x]; } } void join(int x, int y){ int fax = find(x); int fay = find(y); if(fax != fay){ // fa[fax] = fay; } } int main(){ int n, m, p; while(cin >> n >> m >> p){ for(int i = 1; i <= n; i ++){ fa[i] = i; } int x, y; // 读入关系 for(int i = 0; i < m; i ++){ cin >> x >> y; join(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; }并查集
查看题解 查看答案
题目描述
Time Limit: 1000 ms
Memory Limit: 256 mb
如题，现在有一个并查集，你需要完成合并和查询操作。
输入输出格式
输入描述:
第一行包含两个整数 N,M ,表示共有 N 个元素和 M 个操作。 接下来 M 行，每行包含三个整数 Zi,Xi,Yi。 当 Zi=1 时，将 Xi 与 Yi 所在的集合合并。 当 Zi=2 时，输出 Xi 与 Yi 是否在同一集合内，是的输出 Y ；否则输出 N 。 1 <= N <= 10^4 1 <= M <= 2*10^5
输出描述:
对于每一个 Zi =2 的操作，都有一行输出，每行包含一个大写字母，为 Y 或者 N 。
输入输出样例
输入样例#:
复制
4 7 2 1 2 1 1 2 2 1 2 1 3 4 2 1 4 1 2 3 2 1 4
输出样例#:
复制
N Y N Y
#include<bits/stdc++.h> using namespace std; #define N 20005 int fa[N] = {0}; int find(int x){ if(fa[x] == x){ return x; } else{ fa[x] = find(fa[x]); return find(fa[x]); } // while(fa[x] != x){ // x = fa[x]; // } // return x; } void join(int x, int y){ int fax = find(x); int fay = find(y); if(fax == fay){ return; } else{ fa[fax] = fay; return; } } int main(){ int n, m, p; while(cin>>n>>m){ int x, y, z; for(int i = 1; i <= n; i ++){ fa[i] = i;l } for(int i = 0; i < m; i ++){ cin>>z>>x>>y; if(z == 1){ join(x, y); } else{ if(find(x) == find(y)){ cout<<"Y"<<endl; } else{ cout<<"N"<<endl; } } } } }