609 유니온파인드

서로소집합을 찾는, 혹은 그래프끼리 연결되어있지 않는것을 찾는 알고리즘
부모를 먼저자기자신으로 초기화
루트노드를 찾아서 기록한다.
$O(V+Mlog_2V)$

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

# 노드개수만큼 부모테이블 있어야하고 각 부모테이블의 기본값으로 자기자신으로 해야함

무방향그래프에서의 사이클 판별할때 이용가능하다
간선의 각각 노드의 부모노드가 같을때 사이클이 발생한다.
방향이있을때는 dfs로 판별가능하다.

if find_parent(parent, a) = = find_parent(parent, b):
    cycle = True 
    break