3.2节后习题

题目要求

一、判断题

并查集是一种用于处理动态连通性问题的数据结构，它只能用于无向图。

正确

错误

在并查集中，路径压缩操作可以显著提高查找操作的效率。

正确

错误

并查集只能用于判断两个元素是否在同一集合中，不能用于计算集合的大小。

正确

错误

并查集的合并操作（Union）必须按照元素的大小顺序进行。

正确

错误

并查集的时间复杂度为 O(1)。

正确

错误

二、选择题

在并查集中，路径压缩操作的作用是什么？

A增加树的高度

B减少树的高度

C增加集合的数量

D减少集合的数量

并查集的按秩合并（Union by Rank）操作的主要目的是什么？

A保持树的平衡

B增加树的高度

C减少树的节点数量

D增加集合的大小

在并查集中，假设集合中有 n 个元素，经过若干次合并操作后，集合的总数最多为：

An

Bn/2

C1

D无法确定

三、应用题

描述：在一个社交网络中，有 n 个人，编号从 1 到 n。现在有若干条关系，每条关系表示两个人是朋友。如果 A 和 B 是朋友，B 和 C 是朋友，那么 A 和 C 也被认为是朋友。请判断任意两个人是否属于同一个社交圈。

输入格式：

• 第一行包含两个整数 n 和 m，分别表示人数和关系数。
• 接下来 m 行，每行包含两个整数 u 和 v，表示 u 和 v 是朋友。
• 最后一行包含两个整数 x 和 y，表示查询 x 和 y 是否属于同一个社交圈。

输出格式：

• 如果 x 和 y 属于同一个社交圈，输出"YES"；否则输出"NO"。

参考代码：

代码

#include <iostream>
#include <vector>
using namespace std;

class UnionFind {
private:
    vector<int> parent;
public:
    UnionFind(int size) {
        parent.resize(size + 1);
        for (int i = 1; i <= size; i++) {
            parent[i] = i;
        }
    }

    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 路径压缩
        }
        return parent[x];
    }

    void unite(int x, int y) {
        int fx = find(x);
        int fy = find(y);
        if (fx != fy) {
            parent[fy] = fx;
        }
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    UnionFind uf(n);

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        uf.unite(u, v);
    }

    int x, y;
    cin >> x >> y;
    cout << (uf.find(x) == uf.find(y) ? "YES" : "NO") << endl;

    return 0;
}