题解
【入门】是不是亲戚
1 条题解
-
0
#include <iostream> #include <vector> using namespace std; class UnionFind { private: vector<int> parent; public: UnionFind(int n) { parent.resize(n + 1); // 1-indexed for (int i = 1; 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; } } bool isConnected(int x, int y) { return find(x) == find(y); } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, p; cin >> n >> m >> p; UnionFind uf(n); // 构建亲戚关系 for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; uf.unite(a, b); } // 处理询问 for (int i = 0; i < p; i++) { int u, v; cin >> u >> v; if (uf.isConnected(u, v)) { cout << "Yes" << endl; } else { cout << "No" << endl; } } return 0; }
- 1