CSP-S 2019 第一轮 第27题：此程序的时间复杂度是（）。

题目

#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;
}

此程序的时间复杂度是（）。

选项

• A. $O(n)$
• B. $O(\log n)$
• C. $O(n^2)$
• D. $O(n\log n)$

答案

C

题解

答案是 C. \(O(n^2)\)（最坏情况下）。

这段代码使用了并查集。关键在于 getRoot(v) 会沿着 fa 不断向上查找，但没有路径压缩；合并时直接执行 fa[x] = y，也没有按大小或高度合并。因此，并查集可能退化成一条长链，一次查找最坏需要 \(O(n)\)。

例如，依次输入： ``text 0 1 0 2 0 3 ... 0 n-1 ``

合并过程会形成： ``text 0 → 1 0 → 1 → 2 0 → 1 → 2 → 3 ... ``

每次都要调用 getRoot(0)，沿链查找的长度不断增加，所以总耗时为： \[ 1+2+\cdots+(n-1)=\Theta(n^2). \]

初始化只需要 \(O(n)\)，因此整个程序的最坏时间复杂度为 \(O(n^2)\)。