01703: 发现它，抓住它

http://cs101.openjudge.cn/practice/01703/

一个城市中有两个犯罪团伙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条信息。

输出

对于每条需要回答的信息，你需要输出一行答案。如果是同一个团伙所为，回答"In the same gang."，如果不是，回答"In different gangs."，如果不确定，回答”Not sure yet."。

样例输入

样例输出

Not sure yet.
In different gangs.
In the same gang.

这个问题可以通过并查集（Union-Find）数据结构来有效解决。并查集是一种非常适合处理集合合并以及查询两个元素是否在同一个集合中的数据结构。

对于这个问题，我们需要稍微扩展并查集的基本操作以适应犯罪团伙的判断。由于信息中只提到两个案件是否属于不同的团伙，我们可以通过将每个案件关联到两个不同的代表元素来表示这种关系：一个代表与它在同一个团伙的案件的代表元素，另一个代表与它在不同团伙的案件的代表元素。

具体来说，对于每个案件，我们实际上在并查集中维护两个节点：一个代表案件本身，另一个代表其对立案件。当我们得知两起案件属于不同的团伙时，我们将一起案件的案件节点与另一起案件的对立案件节点合并，反之亦然。

实现步骤如下：

初始化并查集，对于N起案件，我们需要2N个节点，因为每起案件有两个节点（本身和对立案件）。
对于每条信息：
- 如果是"D [a] [b]"类型，表示案件a和案件b属于不同团伙，我们将案件a与案件b的对立案件合并，案件b与案件a的对立案件合并。
- 如果是"A [a] [b]"类型，我们需要判断案件a和案件b是否属于同一个团伙：
  - 如果案件a和案件b属于同一个集合，或者案件a的对立案件和案件b的对立案件属于同一个集合，输出"In the same gang."。
  - 如果案件a和案件b的对立案件属于同一个集合，或者案件b和案件a的对立案件属于同一个集合，输出"In different gangs."。
  - 否则，输出"Not sure yet."。

以下是代码实现的核心部分：

python

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            if self.rank[rootX] > self.rank[rootY]:
                self.parent[rootY] = rootX
            elif self.rank[rootX] < self.rank[rootY]:
                self.parent[rootX] = rootY
            else:
                self.parent[rootY] = rootX
                self.rank[rootX] += 1

def solve():
    n, m = map(int, input().split())
    uf = UnionFind(2 * n)  # 初始化并查集，每个案件对应两个节点
    for _ in range(m):
        operation, a, b = input().split()
        a, b = int(a) - 1, int(b) - 1
        if operation == "D":
            uf.union(a, b + n)  # a与b的对立案件合并
            uf.union(a + n, b)  # a的对立案件与b合并
        else:  # "A"
            if uf.find(a) == uf.find(b) or uf.find(a + n) == uf.find(b + n):
                print("In the same gang.")
            elif uf.find(a) == uf.find(b + n) or uf.find(a + n) == uf.find(b):
                print("In different gangs.")
            else:
                print("Not sure yet.")

T = int(input())
for _ in range(T):
    solve()

这段代码首先读取测试用例数量 T，然后对每个测试用例执行 solve 函数，该函数首先创建一个并查集实例，然后根据输入的操作和案件编号更新并查集，并根据并查集的当前状态回答查询。

01703: 发现它，抓住它 ​

01703: 发现它，抓住它