서로소 집합

• 수학에서 서로소 집합이란 공통 원소가 없는 두 집합을 의미한다. 예를 들어 집합{1,2}와 집합{3,4}는 서로 관계이다. 반면에 집합 {1,2}와 집합{2,3}은 2라는 원소가 두 집합에 공통적으로 포함되어 있기 때문에 서로소 관계가 아니다.

• 서로소 집합 자료구조란 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조

• 서로소 집합 구조는 union-find 이 2개의 연산으로 조작할 수 있다.
  - union 연산은 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산
  - find 연산은 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산이다.

  ---

신장 트리

• 신장 트리란? 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미

  ---

• 서로소 집합을 활용한 크루스칼 알고리즘

def find_parent(parent, x):
    
    #루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출

    if parent[x] == x:
        return x

    px = find_parent(parent,parent[x])
    parent[x] = px

    return px


def union(x, y):
    a = find_parent(parent,x)
    b = find_parent(parent,y)

    #더 작은 수의 값을 조상으로,,!
    if a < b:
        parent[b] = a

    else:
        parent[a] = b


v, e = map(int, input().split())

parent = [i for i in range(v + 1)]


edges = []
result = 0

#단반향
for _ in range(e):
    frm, to, cost = map(int, input().split())
    # 비용순으로 정렬하기 위해서 튜플의 첫 번째 원소를 비용으로 설정

    edges.append((cost, frm, to))


edges.sort()

for edge in edges:
    cost, a, b = edge # 오 이렇게 가능!

    # 사이클이 발생하지 않을 경우에만 집합에 포함
    if find_parent(parent,a) != find_parent(parent,b):
        union(a, b)
        result += cost


print(result)

---

위상 정렬

• 정렬 알고리즘의 일종이다. 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다.

위상 정렬이란?
방향 그래프의 모든 노드를 "방향성"에 거스르지 않도록 순서대로 나열하는 것이다.

• 현실세계에서의 위상 정렬을 수행하게 되는 전형적인 예시로는 선수과목을 고려한 학습 순서 설정을 들 수 있다.

예를 들어 컴퓨터 공학과 커리큘럼에는 "자료구조"과목을 수강한 뒤에 "알고리즘"강의를 수강하는 것을 권장한다. 이 때 "자료구조" 및 "알고리즘"을 각각의 노드로 표현하고, "자료구조"에서 "알고리즘"으로 이어질 수 있도록 방향성을 갖는 간선을 그릴 수 있다. 다시 말해 그래프상에서 선후관계가 있다면, 위상 정렬을 수행하여 모든 선후 관계를 지키는 전체 순서를 계산할 수 있다.

---

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

from collections import deque



# 노드의 개수와 간선의 개수를 입력받기
v, e = map(int, input().split())

#모든 노드에 대한 진입차수는 0으로 초기화
indegree = [0] * (v + 1)

#각 노드에 연결된 간성 정보를 담기 위한 연결 리스트(그래프) 초기화 // 1번 노드 부터 탐색이 시작되니깐 v + 1을 한것
graph = [[] for _ in range(v + 1)]

# 단방향 그래프의 모든 간선 정보를 입력받기

for _ in range(e):
    frm, to = map(int, input().split())
    #frm 노드에서 to 노드로 이동이 가능
    graph[frm].append(to)
    #진입 차수를 1 증가
    indegree[to] += 1
    
#위상 정렬 함수

def topology_sort():
    result = [] #알고ㅈ리즘 수행 결과를 담을 리스트
    q = deque()
    
    #처음 시작할 때는 진입 차수가 0인 노드를 큐에 삽입
    for node in range(1, v+1):
        if indegree[node] == 0:
            q.append(node)
            
        
    #큐가 빌때까지 반복

    while q:

        now = q.popleft()
        #여기서 결과를 담는군!
        result.append(now)
        
        #해당 원소와 연결된 노드들의 진입차수에서 1 빼기
        for next in graph[now]:
            indegree[next] -= 1
            #새롭게 진입차수가 0이 되는 노드를 큐에 삽입
            if indegree[next] == 0:
                q.append(next)
                
    #위상 정렬를 수행한 결과 출력

    for node in result:
        print(node, end=" ")

topology_sort()