[대표 유형] 크루스칼 알고리즘

문제 설명

정점의 개수 n, 양방향 간선 정보가 담긴 edges가 매개 변수로 주어질 때 크루스칼 알고리즘을 적용하여 최소 신장 트리에 포함되는 간선 번호를 순서대로 반환하는 solution 함수를 작성하시오.

만일 크루스칼 알고리즘을 진행하며 간선의 가중치가 같은 간선이 있다면 간선 번호가 작은 간선부터 탐색하시오.

간선 번호는 edges로 주어진 간선 정보의 순서로 결정됩니다.
(edges로 주어진 첫 번째 간선의 번호는 1, 두 번째 간선의 번호는 2, ...)

그래프는 연결그래프(임의의 두 정점 사이에 경로가 존재하는 그래프)만 주어진다고 가정합니다.
그래프는 항상 최소 신장 트리가 존재하는 경우만 주어진다고 가정합니다.

개념 설명

최소 신장 트리(Minimum Spanning Tree)는 주어진 양방향 그래프에 대하여 간선의 가중치 총합이 최소인 신장 트리를 의미합니다.
참고 : [대표 유형] 최소 신장 트리

최소 신장 트리를 구하는 알고리즘으로는 프림 알고리즘과 크루스칼 알고리즘이 있습니다.

크루스칼 알고리즘은 다음과 같은 과정으로 진행됩니다.

1. E개의 간선을 간선의 가중치를 기준으로 오름차순 정렬합니다.
2. 가중치가 가장 작은 간선부터 간선의 양 끝점이 이미 연결되어 있는지 확인합니다.
3. 만일 간선의 양 끝점이 이미 연결되어 있을 경우 해당 간선을 선택하지 않고, 연결되어 있지 않은 경우 해당 간선을 선택하여 두 정점을 연결합니다.
4. 모든 정점이 연결될 때까지 2~3 과정을 반복합니다.

크루스칼 알고리즘은 $O(Elog V)$의 시간 복잡도를 갖습니다.

예를 들어 다음과 같은 연결그래프가 있고 크루스칼 알고리즘으로 MST를 구한다고 가정합니다. 간선 번호는 입력을 순서대로 주어지며 X,Y는 각 정점의 번호를 의미합니다.

이를 가중치를 기준으로 오름차순 정렬한 결과는 다음과 같습니다. 이때 동일한 가중치를 갖는 경우 간선 번호를 기준으로 오름차순 정렬합니다.

이후 낮은 가중치의 간선부터 차례로 간선의 양 끝점이 서로 연결되어 있는지 확인하며 MST를 구성합니다. 첫 번째 8번 간선의 경우에는 6번 정점과 3번 정점이 연결되어 있지 않으므로 MST에 포함됩니다.

다음으로 6번 간선의 경우에는 3번 정점과 2번 정점이 연결되어 있지 않으므로 MST에 포함됩니다.

동일한 방법으로 2번 간선과 1번 간선도 차례대로 MST에 포함됩니다.

다음으로 7번 간선의 경우 현재까지 구성된 MST에서 이미 2번 정점과 4번 정점이 연결되어 있으므로 MST에 포함되지 않습니다.

찬가지로 3번 간선 또한 이미 4번 정점과 6번 정점은 서로 연결되어 있으므로 MST에 포함되지 않습니다.

반면 5번 간선은 새롭게 MST에 추가됩니다.

이와 같은 과정으로 모든 간선에 대해 탐색하거나 MST를 모두 이루게 되면 알고리즘을 종료합니다.

제한 사항

• 정점의 개수 n은 2 이상 50,000 이하의 자연수입니다.
• 양방향 간선 정보 edges의 원소는 특정 간선의 양 끝 정점 x, y와 간선의 가중치 w로 이루어집니다.
  • edges는 최대 200,000개의 간선 정보로 이루어집니다.
  • x, y는 1 이상 n 이하의 자연수입니다.
  • w는 10,000 이하의 자연수입니다.

예시 테스트케이스 설명

1번 테스트케이스 설명

• 위에서 제시된 예시와 동일합니다.

2번 테스트케이스 설명

• 주어진 그래프는 트리이며 모든 간선이 최소 신장 트리에 포함되어 간선의 가중치 순서대로 최소 신장 트리에 추가됩니다.