AcWing 237. 程序自动分析
原题链接
中等
作者:
acwing_62485
,
2025-04-16 21:16:47
· 中国香港
,
所有人可见
,
阅读 1
# 维护两个并查集
from collections import defaultdict
# 如果最终两个数在同一集合内,相同
# 如果不在同一集合内,不同
t = int(input())
maxN = 200010
def find(x):
if p[x] != x: p[x] = find(p[x])
return p[x]
for _ in range(t):
n = int(input())
p = [__ for __ in range(maxN)]
Tag = False
dic = defaultdict(set)
cnt = 1
exist = defaultdict(int)
for __ in range(n):
i, j, e = map(int, input().split())
if i not in exist:
exist[i] = cnt
cnt += 1
if j not in exist:
exist[j] = cnt
cnt += 1
dic[e].add((exist[i], exist[j]))
# 把所有相等的数合并到各自的集合内
for i, j in dic[1]:
pi, pj = find(i), find(j)
# i == j
p[pi] = pj
for i, j in dic[0]:
# i != j
pi, pj = find(i), find(j)
if p[pi] == p[pj]:
print('NO')
Tag = True
break
if Tag: continue
print('YES')