백준 16562. 친구비

https://www.acmicpc.net/problem/16562

16562번: 친구비

 

크루스칼로 mst를 만들면 된다. 

좀 신경써야 할 부분은 입력조건에서 다음 부분이다 

 

다음 M개의 줄에는 숫자 v, w가 주어진다. 이것은 학생 v와 학생 w가 서로 친구라는 뜻이다. 자기 자신과 친구일 수도 있고, 같은 친구 관계가 여러 번 주어질 수도 있다.

 

크루스칼 알고리즘을 수행한후에 mst가 만들어졌는지 판단하는 방법은 최종적으로 간선의 갯수가 노드의 갯수보다 하나 작다면 정상적으로 mst가 만들어진 것이다. 

따라서 입력에서 친구 관계가 주어질 때부터 간선의 갯수를 세어야 한다. 

그런데 위 조건 때문에 그냥 친구관계가 주어질때마다 간선의 갯수를 세어주면 안된다는 것을 알 수 있다.

따라서 크루스칼 알고리즘 처럼 부모가 같은지 확인하고 아니면 간선을 연결하면서 간선의 갯수도 늘려주면 된다.

 

크루스칼 알고리즘을 돌릴때는 나를 0번 노드로 하고, 친구비가 적은 친구부터 0번과 이어주면 되는데 돈이 부족하면 종료하면 된다.

 

최종적으로 크루스칼 알고리즘 수행 이후 간선의 갯수가 N개라면 MST가 만들어진 것이고 아니라면 못만든 것이다.