問題
연결된 무방향 그래프가 주어졌을 때,이 그래프의 최소 신장 트리(Minimum Spanning Tree, 이하 MST) 가 유일한지를 판별하시오.
신장 트리는 다음과 같이 정의한다
- 연결된, 무방향그래프 G = (V, E)가 있다. 여기서 V는 모든 정점의 집합, E는 모든 간선의 집합을 뜻한다. - G의 신장 트리는 G의 부분그래프로서, 다음과 같은 특성을 따르는 T = (V', E')라 칭한다.
1. V' = V. 2. T는 연결되어 있고 싸이클이 없다.
MST는 다음과 같이 정의한다.
간선의 가중치가 있는 연결된 무방향그래프 G = (V, E)를 생각해보자.
G의 최소 스패닝 트리 T = (V, E')는 가중치의 합이 가장 작은 스패닝트리이다.
T의 가중치의 합이란 모든 간선 E'의 가중치를 더한 값을 의미한다.
入力
테스트 케이스의 수 t(1≤t≤20)이 첫 줄에 주어지고, 각각의 케이스들은 한 그래프를 나타낸다. 각각의 케이스는 두 개의 정수 n, m(1≤n≤100)으로 시작된다. n은 노드의 수, m은 간선의 수이다. 그 뒤로 m줄에는 (xi, yi, wi)가 주어지는데, xi와 yi가 wi라는 가중치를 가지고 연결되어 있다는 뜻이다. 임의의 두 노드는 많아야 한 개의 간선만을 가진다.
出力
각각의 입력에 대해 만약 MST가 유일하다면 MST의 값을 출력하고, 유일하지 않다면 "Not Unique!"를 출력한다.
例題
2
3 3
1 2 1
2 3 2
3 1 3
4 4
1 2 2
2 3 2
3 4 2
4 1 2
3
Not Unique!
ログインしないとコードを書けません。