本文共 2131 字，大约阅读时间需要 7 分钟。
为了解决这个问题，我们需要帮助科学家确定森林中树的数量，并判断每对鸟是否在同一棵树上。我们可以使用并查集（Union-Find）数据结构来高效地解决这个问题。
#include#include using namespace std;void findFather(int x, vector & fa) { if (!fa[x]) { // 不存在的情况下返回0 return 0; } int a = x; while (x != fa[x]) { x = fa[x]; } while (a != fa[a]) { int z = a; a = fa[a]; fa[z] = x; } return x;}void unionBirds(int x, int y, vector & fa) { int rootX = findFather(x, fa); int rootY = findFather(y, fa); if (rootX == 0 || rootY == 0) { // 不存在的情况 return; } if (rootX != rootY) { fa[rootY] = rootX; }}int main() { int n, q; cin >> n; vector fa(maxn, -1); // 初始化父数组 vector exist(maxn, false); // 存在标记 vector cnt(maxn, 0); // 计数器数组 for (int i = 0; i < n; ++i) { int k, id; cin >> k >> id; exist[id] = true; for (int j = 1; j < k; ++j) { int m; cin >> m; exist[m] = true; unionBirds(id, m, fa); } } int totalTrees = 0; int totalBirds = 0; for (int i = 1; i < maxn; ++i) { if (exist[i]) { int root = findFather(i, fa); if (root != 0 && cnt[root] == 0) { cnt[root]++; totalTrees++; totalBirds += k; // 这里可能有问题，需要重新计算 } } } // 修正总鸟数计算方式，遍历所有存在的鸟 int currentTotalBirds = 0; for (int i = 1; i < maxn; ++i) { if (exist[i]) { currentTotalBirds++; } } totalBirds = currentTotalBirds; cout << totalTrees << " " << totalBirds << endl; cin >> q; for (int i = 0; i < q; ++i) { int bird1, bird2; cin >> bird1 >> bird2; if (bird1 == 0 || bird2 == 0) { cout << "No"; continue; } int root1 = findFather(bird1, fa); int root2 = findFather(bird2, fa); if (root1 == root2) { cout << "Yes"; } else { cout << "No"; } } return 0;}
该方法通过并查集高效地解决问题，能够处理大量数据，确保查询的高效性。
转载地址：http://antuz.baihongyu.com/