这里,n 是强盗的数量,2*n+1 是数组 p 的大小,它足够容纳所有强盗以及他们的“影子”(shadow)强盗。每个强盗 i 都有一个对应的“影子”强盗 i+n。这样做的目的是为了区分朋友关系和敌人关系,因为并查集只能处理合并操作,不能直接处理“不是朋友”的关系。
当 op == ‘F’ 时,表示 a 和 b 是朋友,我们直接合并 a 和 b 的根节点。
当 op == ‘E’ 时,表示 a 和 b 是敌人。我们不能直接合并 a 和 b,因为这样会违反题目中的规则。相反,我们合并 a 的“影子”和 b,以及 b 的“影子”和 a。这样,即使 a 和 b 在同一个团伙中,他们的“影子”也会在不同的团伙中,从而确保 a 和 b 不会直接成为朋友。
通过这种方式,我们可以确保:
如果 a 和 b 是朋友,他们将被合并到同一个团伙中。
如果 a 和 b 是敌人,他们将通过他们的“影子”间接地成为朋友,但不会直接合并,从而保持敌人关系。
最后,我们遍历 p 数组,统计根节点的数量,这代表了最大可能的团伙数。每个根节点代表一个独立的团伙,因为它们没有被合并到其他团伙中。这就是为什么 res 变量用于计数根节点,即团伙的数量。
import sys
def find(x):
if p[x]!=x:
p[x]=find(p[x])
return p[x]
n=int(sys.stdin.readline())
p=[i for i in range(10001)]
res=0
tree=0
max_=0 #优化查找有多少棵树
for _ in range(n):
a=list(map(int,sys.stdin.readline().strip().split()))
b,a=a[0],a[1:]
max_=max(max_,max(a))
for i in range(1,len(a)):
if find(a[i-1])!=find(a[i]):
p[find(a[i])]=find(a[i-1])
res+=1
for i in range(1,max_+1):
if p[i]==i:
tree+=1
q=int(sys.stdin.readline())
print(tree,tree+res)
for i in range(q):
a,b=map(int,sys.stdin.readline().strip().split())
if find(a)==find(b):
print('Yes')
else:
print('No')