그래프 이론

커리큘럼 # ㅠ.ㅠ 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) edges = [] result = 0 for i in range(1,v+1): ..

도시 분할 계획 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 n, m = map(int, input().split()) parent = [0] * (n+1) for i in range(n+1): parent[i] = i edges = [] r..

팀 결성 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 n, m = map(int, input().split()) parent = [0] * (n+1) for i in range(n+1): parent[i] = i for _ in range(m..

위상 정렬 정렬 알고리즘의 일종으로, 순서가 정해져 있는 일련의 작업을 차례대로 수행해야할 때 사용할 수 있는 알고리즘 다시 말해, 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것'이다. 위상 정렬 알고리즘은 다음과 같다. 진입차수가 0인 노드를 큐에 넣는다. 큐가 빌 때까지 다음의 과정을 반복한다. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다. 큐에서 원소가 V번 추출되기 전에 큐가 비어버리면 사이클이 발생한 것이다. 다만, 기본적으로 위상 정렬 문제에서는 사이클이 발생하지 않는다고 명시하는 경우가 많다. from..