CSP-S 2019 第一轮 第23题：第 16 行改成 fa[i] = 0;，不影响程序运行结果

题目

#include <iostream>
using namespace std;

const int maxn = 1000;
int n;
int fa[maxn], cnt[maxn];

int getRoot(int v) {
    if (fa[v] == v) return v;
    return getRoot(fa[v]);
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        fa[i] = i;
        cnt[i] = 1;
    }
    int ans = 0;
    for (int i = 0; i < n - 1; ++i) {
        int a, b, x, y;
        cin >> a >> b;
        x = getRoot(a);
        y = getRoot(b);
        ans += cnt[x] * cnt[y];
        fa[x] = y;
        cnt[y] += cnt[x];
    }
    cout << ans << endl;
    return 0;
}

（1 分）第 16 行改成 fa[i] = 0;，不影响程序运行结果。（）

选项

• T. 正确
• F. 错误

答案

F

题解

选 F（错误）。

fa[i] = i; 表示初始时每个点各自属于一个集合，每个集合大小为 cnt[i] = 1。

改成 fa[i] = 0; 后，所有点的根都是 0，因此每次执行 getRoot(a) 和 getRoot(b)，都会得到 x = y = 0，改变计算结果。

例如输入： ``text 3 0 1 1 2 ``

• 原程序：两次分别给 ans 加上 1×1=1 和 2×1=2，输出 3。
• 修改后：第一次加上 1×1=1，随后 cnt[0] 加倍为 2；第二次加上 2×2=4，输出 5。

输出不同，所以题目中的说法错误。