8. 기타 그래프 이론: 사이클 판별

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()) #노드개수v,간선개수e
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("사이클 안발생")

간선 정보를 입력받는다

노드 a,b의 부모노드가 다른경우 

union(합집합)연산을 수행하고

노드a,b의 부모노드가 같은 경우

사이클이 발생한 것이므로 반복을 중단