그래프(union-find, 크루스칼)

서로소 집합.

• 공통원소가 없는 두 집합.

이용하는 함수 두 가지.

1. union - find 함수
2. find 함수(root 노드를 찾는 함수)

동작과정

1. union 연산을 확인해, 서로 연결된 두 노드 A, B를 확인.
   -1. A와 B의 루트 노드 A', B'를 각각 찾기.
   -2. A' 를 B'의 부모노드로 설정.(부모노드의 경우 수가 더 작은 거를 부모노드로 설정.)
2. 모든 연산을 처리 할때 까지 1번 반복.

가장 필요한 변수는. 부모노드를 나타내는 리스트가 필요.
. 루트 노드를 찾기 위해선 재귀적으로 부모를 거슬러 올라감.

def find_parent(parent, x):
    if parent[x] != x:
        find_parent(parent, parent[x])
    return x

def union(parent, a, b):
    root_a = find_parent(parent, a)
    root_b = find_parent(parent, b)
    if root_a < root_b:
        parent[b] = root_a
    else:
        parent[a] = root_b
        
node, edge_num = map(int, input().split())
parent = [0] * (node + 1)

for i in range(len(parent)):
    parent[i] = i

for i in range(edge_num):
    A, B = map(int, input().split())
    union(parent, A, B)

find 함수 : 현재 노드의 루트 노드를 찾아냄.
parent 리스트 : 자기 바로 위의 부모 노드를 가지고 있음.

경로 압축 기법.

find 함수에서 재귀를 이용하는 것이 시간 복잡도를 많이 잡아 먹는다.
이를 보완 하기 위해 부모 노드를 나타내는 parent 리스트를 업데이트하는 방식이다.

def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return x

사이클 판별.

1. 각 간선을 확인하며 두 노드의 루트 노드를 확인
   -1. 루트 노드가 서로 다르면 union 연산 수행
   -2. 서로 같다면 사이클이 발생.
2. 1번 과정을 반복.

def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return x

def union(parent, a, b):
    root_a = find_parent(parent, a)
    root_b = find_parent(parent, b)
    if root_a < root_b:
        parent[b] = root_a
    else:
        parent[a] = root_b

node, edge_num = map(int, input().split())
parent = [0] * (node + 1)

for i in range(len(parent)):
    parent[i] = i
# 다른 부분은 동일 하지만
# 아래 부분만 다르다.
# 부모 노드가 같은 경우엔 브레이크 하고 바로 나간다.
-------------------------------------------------------------------------------------------------
cycle = False

for i in range(edge_num):
    A, B = map(int, input().split())
    if find_parent(parent, A) == find_parent(parent, B):
        cycle = True
        break
    else:
        union(parent, A, B)
-------------------------------------------------------------------------------------------------

신장트리

신장트리란?
하나의 그래프가 모든 노드를 포함하며 사이클이 존재하지 않는 부분.

크루스칼

최소한의 비용으로 신장트리를 찾는 것.
가장 중요한 부분은 모든 간선에 대해 정렬을 수행해야 하는 것.

동작과정

1. 간선 데이터를 비용에 따라 오름차순으로 정렬.
2. 간선을 확인 하며 사이클을 발생시키는지 확인
   -1. 사이클 X , 최소 신장 트리에 포함
   -2. 사이클 O , 최소 신장 트리에 포함시키지 않는다.
3. 모든 간선에 대해 2번 반복.

언제나 성립하는 것으로 신장트리에 포함되는 간선의 수는 '노드의 개수 -1'이다.(당연한 소리쥬.)
ex) 노드 7개를 간선으로 연결하려면 6개의 간선이 필요하니까.

def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return x

def union(parent, a, b):
    root_a = find_parent(parent, a)
    root_b = find_parent(parent, b)
    if root_a < root_b:
        parent[b] = root_a
    else:
        parent[a] = root_b

node, edge_num = map(int, input().split())
parent = [0] * (node + 1)

for i in range(len(parent)):
    parent[i] = i

edges = []
results = 0

for i in range(edge_num):
    A, B, cost = map(int, input().split())
    edges.append((cost, A, B))
    
# 정렬을 수행.
# 루트 노드들이 다른 것의 경우 사이클이 발생하지 않는다.
# 그러한 노드들 만을 모아 결과를 출력
-------------------------------------------------------------------------------------------------    
edges.sort()

for item in edges:
    cost, a, b = item
    if find_parent(parent, a) != find_parent(parent, b):
        results += cost
        union(parent, a, b)

print(results)
-------------------------------------------------------------------------------------------------

위상 정렬

일련의 작업을 차례대로 수행해야 할 때 사용하는 알고리즘.(방향성을 거스르지 않도록 나열)
방향성을 가지기에 노드는 진입 차수를 가진다.

진입차수란?
특정한 노드로 들어오는 간선의 개수를 의미한다.

그래서 진입차수를 나타낼 리스트가 필요.
이를 indegree 라 부르자.

동작 과정

1. 진입차수가 0인 노드를 큐에 넣는다.
2. 큐가 빌 때 까지 다음의 과정을 반복한다.
   -1. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거.
   -2. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.

모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재.(한번 그려서 해결 해 보도록 하자. 쿸쿠)
진입차수가 0이 안 되면 큐에 들어가지 못하는데 사이클이 존재할 경우 0이 되지 않기 떄문임.

from _collections import deque

node, edge_num = map(int, input().split())
#진입차수의 초기화가 필요하다 
indegree = [0] * (node + 1)
graph = [[] for i in range(node + 1)]

for _ in range(node):
    a, b = map(int, input().split())
    graph[a].append(b)
    indegree[b] += 1
    
def topology_sort():
    #정렬된 값들을 담을 리스트
    result = []
    q = deque()
    
    #진입차수가 0인 것을 큐에 담기.
    for idx, item in enumerate(indegree):
        if not item:
            q.append(idx)
    
    while q:
        now = q.popleft()
        result.append()
        for data in graph[now]:
            indegree[data] -= 1
            if not indegree[data]:
                q.append(data)

    for i in result:
        print(i, end=" ")
    
topology_sort()