发现它，抓住它 显示标签 时间限制：C/C++ 1000MS，其他语言 2000MS 内存限制：C/C++ 256MB，其他语言 512MB 难度：基础 分数：100 OI排行榜得分：14(0.1*分数+2*难度) 出题人： 描述 一个城市中有两个犯罪团伙A和B，你需要帮助警察判断任意两起案件是否是同一个犯罪团伙所为，警察所获得的信息是有限的。假设现在有N起案件（N<=100000），编号为1到N，每起案件由团伙A或团伙B所为。你将按时间顺序获得M条信息（M<=100000），这些信息分为两类： D [a] [b] 其中[a]和[b]表示两起案件的编号，这条信息表明它们属于不同的团伙所为 A [a] [b] 其中[a]和[b]表示两起案件的编号，这条信息需要你回答[a]和[b]是否是同一个团伙所为 注意你获得信息的时间是有先后顺序的，在回答的时候只能根据已经接收到的信息做出判断。 输入描述 第一行是测试数据的数量T（1<=T<=20）。 每组测试数据的第一行包括两个数N和M，分别表示案件的数量和信息的数量，其后M行表示按时间顺序收到的M条信息。 输出描述 对于每条需要回答

```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)$。 [2026-02-02 17:28:01 | AI问答 | 894点数解答]