巧用并查集：判断犯罪团伙案件归属，代码详解与复杂度分析

```cpp #include <iostream> #include <vector> using namespace std; // 并查集类，用于处理集合合并和查找操作 class UnionFind { private: vector<int> parent; vector<int> relation; public: // 构造函数，初始化并查集 UnionFind(int n) { parent.resize(n + 1); relation.resize(n + 1); for (int i = 1; i <= n; ++i) { parent[i] = i; relation[i] = 0; } } // 查找根节点并进行路径压缩 int find(int x) { if (x != parent[x]) { int px = parent[x]; parent[x] = find(parent[x]); relation[x] = (relation[x] + relation[px]) % 2; } return parent[x]; } // 合并两个元素所在的集合 void unite(int x, int y) { int px = find(x); int py = find(y); if (px != py) { parent[px] = py; relation[px] = (relation[x] + relation[y] + 1) % 2; } } // 判断两个元素的关系 string judge(int x, int y) { int px = find(x); int py = find(y); if (px != py) { return "Not sure yet."; } if (relation[x] == relation[y]) { return "In the same gang."; } return "In different gangs."; } }; int main() { int T; cin >> T; while (T--) { int n, m; cin >> n >> m; UnionFind uf(n); for (int i = 0; i < m; ++i) { char op; int a, b; cin >> op >> a >> b; if (op == 'A') { cout << uf.judge(a, b) << endl; } else if (op == 'D') { uf.unite(a, b); } } } return 0; } ``` 代码解释： 1. 并查集类 `UnionFind`： - `parent` 数组用于记录每个元素的父节点，`relation` 数组用于记录元素与根节点的关系（0 表示在同一团伙，1 表示在不同团伙）。 - `find` 函数用于查找元素的根节点，并进行路径压缩，同时更新 `relation` 数组。 - `unite` 函数用于合并两个元素所在的集合，更新父节点和关系。 - `judge` 函数用于判断两个元素是否在同一团伙，根据根节点和关系数组输出相应结果。 2. 主函数 `main`： - 读取测试数据的数量 `T`。 - 对于每组测试数据，读取案件数量 `n` 和信息数量 `m`。 - 初始化并查集 `uf`。 - 循环读取每条信息，根据信息类型进行相应处理： - 如果是 `A` 操作，调用 `judge` 函数输出结果。 - 如果是 `D` 操作，调用 `unite` 函数合并两个元素所在的集合。 复杂度分析： - 时间复杂度：并查集的查找和合并操作的平均时间复杂度接近 $O(1)$，因此总的时间复杂度为 $O(M \alpha(N))$，其中 $\alpha(N)$ 是阿克曼函数的反函数，近似为常数。 - 空间复杂度：主要使用了 `parent` 和 `relation` 数组，空间复杂度为 $O(N)$。 ######[AI问答 | 894点数解答 | 2026-02-02 17:28:01]