서로소집합

[c++] 백준 1197 풀이 (MST, 최소 신장 트리, 그래프, 유니온 파인드)

이번에는 MST를 풀어보자. MST는 Minimum Spanning Tree의 약자로 span이란 기간을 의미해서 직역하면 최소화된 기간 트리이다. 좀 더 풀어 말하면 트리가 낮은 가중치로 연결되어 있다고 볼 수 있다. 다르게는 그래프의 최소 연결 부분 그래프 라고 할 수 있다. 이번 문제를 풀기 위해서는 MST를 알기 이전에 Spanning Tree에 대해서 이해해야한다. Spanning Tree 간선 수가 가장 작게 연결된다. 만약 정점이 V개라면 V-1개로 연결된 트리 사이클이 존재하지 않는다.(트리의 형태) Minimum Spanning Tree 값이 가장 작은 간선을 이용하여 만든 Spanning Tree 간선 가중치 합이 최소여야 한다. 사이클이 존재하지 않는다. 크루스칼 알고리즘과 프림알고리..