Dev On The Coffee Dev On The Coffee

# 문제 내 풀이 - 수정 답안 import sys input = sys.stdin.readline # 특정 원소가 속한 집합을 찾기 (Find 연산) def find_parent(parent, x): if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return parent[x] # 두 원소가 속한 집합을 합치기 (Union 연산) 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= int(input()) loc = [] # 좌표를 입력 받을 리스트 edges..

# 문제 내 풀이 from itertools import combinations import sys input = sys.stdin.readline # 특정 원소가 속한 집합을 찾기 (Find 연산) def find_parent(parent, x): if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return parent[x] # 두 원소가 속한 집합을 합치기 (Union 연산) 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, inp..

# 문제 내 풀이 from itertools import combinations import sys input = sys.stdin.readline # 특정 원소가 속한 집합을 찾기 (Find 연산) def find_parent(parent, x): if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return parent[x] # 두 원소가 속한 집합을 합치기 (Union 연산) 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 = int(input()) lo..

# 문제 내 풀이 import sys input = sys.stdin.readline # 특정 원소가 속한 집합을 찾기 (Find 연산) def find_parent(parent, x): if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return parent[x] # 두 원소가 속한 집합을 합치기 (Union 연산) 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 # 노드의 개수와 간선(Union 연산)의 개수 입력 받기 v, e = map(int, input..

# 신장 트리(Spanning Tree)란? 신장 트리(Spanning Tree)란 원본 그래프의 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 뜻한다. 위의 가운데 그림처럼 간선들이 모든 노드를 잇고 있지만, 사이클은 생기지 않는 부분 그래프가 신장 트리의 예시가 된다. 반면, 오른쪽 그림처럼 모든 노드를 잇지도 않고 사이클마저 생기는 것은 신장 트리에 해당되지 않는다. 이 개념을 트리라고 부르는 이유는 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건이 트리의 조건에 해당하기 때문이다. 이러한 트리의 특성으로 인해, 신장 트리가 가지는 총 간선의 개수는 노드의 개수 - 1이 된다. # 최소 신장 트리(MST, Minimum Spanning Tree) 최소 신장 트리(..