: 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조
- 합집합 연산을 확인하여, 서로 연결된 두 노드 A,B를 확인
- 모든 합집합 연산을 처리할 때까지 1번의 과정을 반복
def find_parent(parent,x):
if parent[x]!=x:
return find_parent(parent,parent[x])
return x
def union_parent(parent,a,b):
a=find_parent(parent,a)
b=find_parent(parent,b)
if a<b:
parent[b]=a
else:
parent[a]=b
v,e = map(int,input().split())
parent = [0]*(v+1)
for i in range(1,v+1):
parent[i]=i
for i in range(e):
a,b= map(int,input().split())
union_parent(parent,a,b)
print('각 원소가 속한 집합: ', end= ' ')
for i in range(1,v+1):
print(find_parent(parent,i), end = ' ')
print()
print('부모 테이블: ',end='')
for i in range(1,v+1):
print(parent[i],end=' ')
def find_parent(parent,x):
if parent[x]!=x:
parent[x]=find_parent(parent,parent[x])
return parent[x]
def union_parent(parent,a,b):
a=find_parent(parent,a)
b=find_parent(parent,b)
if a<b:
parent[b]=a
else:
parent[a]=b
v,e = map(int,input().split())
parent = [0]*(v+1)
for i in range(1,v+1):
parent[i]=i
for i in range(e):
a,b,=map(int,input().split())
union_parent(parent,a,b)
print('각 원소가 속한 집합 : ',end='')
for i in range(1,v+1):
print(find_parent(parent,i),end= ' ')
print()
print('부모 테이블: ',end="")
for i in range(1,v+1):
print(parent[i],end=' ')
v,e = map(int,input().split())
parent = [0]*(v+1)
for i in range(1,v+1):
parent[i]=i
cycle = False
for i in range(e):
a,b= map(int,input().split())
if find_parent(parent,a)==find_parent(parent,b):
cycle = True
break
else:
union_parent(parent,a,b)
if cycle:
print("사이클이 발생했습니다.")
else:
print("사이클이 발생하지 않았습니다.")