CSP-S 2019 第一轮 第22题：（1分）输入的a和b 值应在[θ，n-1]的范围内。（)

题目

#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 分）输入的 $a$ 和 $b$ 值应在 $[0, n-1]$的范围内。（）

选项

• T. 正确
• F. 错误

答案

T

题解

选 T（正确）。

初始化循环 for (int i = 0; i < n; ++i) 只为编号 0 到 n-1 的元素设置了父节点和计数。

输入的 a、b 是元素编号，会传入 getRoot()，用于访问 fa 数组，因此它们应在 [0, n-1] 范围内。

注意：maxn = 1000 是数组容量，n 才是本次实际使用的元素个数。