共48道题，当前是第20题

初赛真题

01 #include <bits/stdc++.h>
02 using namespace std;
03 int i, j, k, n, m, f[10010], p1, p2, p3;
04 int find(int k) {
05     if (f[k] == k) return k;
06     return f[k] = find(f[k]);
07 }
08 int main() {
09     cin >> n >> m;
10     for (i = 1; i <= n; i++) f[i] = i;
11     for (i = 1; i <= m; i++) {
12         cin >> p1 >> p2 >> p3;
13         if (p1 == 1) f[find(p2)] = find(p3);
14         if (p1 == 2)
15             if (find(p2) == find(p3)) printf("Y\n");
16             else printf("N\n");
17     }
18     return 0;
19 }

1. A。
2. B。
3. A。
4. A。
5. A。
6. B。

该段代码是一个比较朴素的并查集。当输入的 $p1$ 是 $1$ 时表示对并查集执行合并操作。是 $2$ 时表示查询输入的两个元素是否处于同一个集合内部。对于并查集的初始化 f[i]=i 是不可忽略的，因为每个元素都自成一个集合。并查集的复杂度在只应用路经压缩时单次操作是均摊 $O(logn)$ 的，如果没有路径压缩则在最坏情况下单次操作复杂度为 $O(n)$。

Question

1. 该算法中 p1 的作用是确定操作类型

2. 去掉第 10 行 for(i=1;i<=n;i++) f[i]=i; 对该算法没有影响

3. 输入 2 1 2 1 2 输出为 N

4. 输入 2 2 1 1 2 2 1 2 输出为 Y

5. 该算法最坏时间复杂度为( )

6. 把 return f[k]=find(f[k]); 改成 return find(f[k]); 最差时间复杂度为( )