请用C++讲解以下题目:# 亲戚## 题目背景若某个家族人员过于庞大要判断两个是否是亲戚确实还很不容易现在给出某个亲戚关系图求任意给出的两个人是否具有亲戚关系。## 题目描述规定:$x$ 和 $y$ 是亲戚$y$ 和 $z$ 是亲戚那么 $x$ 和 $z$ 也是亲戚。如果 $x$$y$ 是亲戚那么 $x$ 的亲戚都是 $y$ 的亲戚$y$ 的亲戚也都是 $x$ 的亲戚。## 输入格式第一行:三个整
#include <iostream>
#include <vector>
using namespace std;
// 并查集的数据结构
class UnionFind {
public:
vector<int> parent;
UnionFind(int n) {
parent.resize(n);
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
void unite(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
parent[rootX] = rootY;
}
}
};
int main() {
int n, m, p;
cin >> n >> m >> p;
UnionFind uf(n);
for (int i = 0; i < m; i++) {
int Mi, Mj;
cin >> Mi >> Mj;
uf.unite(Mi - 1, Mj - 1);
}
for (int i = 0; i < p; i++) {
int Pi, Pj;
cin >> Pi >> Pj;
if (uf.find(Pi - 1) == uf.find(Pj - 1)) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
}
return 0;
}
``
原文地址: http://www.cveoy.top/t/topic/h06N 著作权归作者所有。请勿转载和采集!