Union Find
6739 ワード
関連する問題
白駿#1717-集合の表現
import sys
n, m = map(int, sys.stdin.readline().split())
root = []
rank = []
def find(x):
if root[x] == x:
return x
else:
root[x] = find(root[x])
return find(root[x])
def union(x, y):
x = find(x)
y = find(y)
if x == y:
return
if rank[x] > rank[y]:
root[y] = x
else:
root[x] = y
if rank[x] == rank[y]:
rank[y] += 1
for i in range(n + 1):
root.append(i)
rank.append(0)
for _ in range(m):
op, a, b = map(int, sys.stdin.readline().split())
if op == 0:
union(a,b)
else:
a = find(a)
b = find(b)
if a == b:
print("YES")
else:
print("NO")
条件をよく知る集合n+1個
白俊は変なところで怒っている.
Reference
この問題について(Union Find), 我々は、より多くの情報をここで見つけました https://velog.io/@0hhanum/Union-Findテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol