tose33

https://www.acmicpc.net/problem/14621 14621번: 나만 안되는 연애 입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 www.acmicpc.net 크루스칼 알고리즘으로 최소 스패닝 트리를 만들면 되는데, 두 노드를 이을때 두 노드의 성별이 다른지도 확인해주면 된다.

https://www.acmicpc.net/problem/15971 15971번: 두 로봇 2018년 강원도에서 새로운 동굴이 발견되었다. 이 동굴에는 총 N개의 넓은 방이 존재하며 좁은 통로로 서로 연결되어 있는 것으로 밝혀졌다. N개의 방은 1번부터 N번까지의 번호를 붙여 1번 방, 2번 www.acmicpc.net 설명을 보면 주어지는 그래프는 최소 스패닝 트리 (MST) 이다. 그렇다면 하나의 노드에서 다른 노드까지의 경로는 유일하다. 따라서 하나의 로봇에서 다른 로봇까지의 경로를 알아내고, 임의의 통로의 양 끝에 위치한 두 방들도 그 통로 위에 위치해 있다고 간주한다 라고 했으므로 경로중 가장 가중치가 큰 통로의 양끝에서 만나면 된다.

https://www.acmicpc.net/problem/16398 16398번: 행성 연결 홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다. 두 행성 간에 플로우를 설치하면 제국의 함 www.acmicpc.net MST (최소 스패닝 트리) 를 만들면 된다. 최소 비용 간선부터 연결할수 있으면 연결하고 연결된 간선의 갯수가 총 노드 갯수 -1 개가 되면 모든 노드들이 연결된 MST가 완성된다.

https://www.acmicpc.net/problem/16562 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10, www.acmicpc.net 크루스칼로 mst를 만들면 된다. 좀 신경써야 할 부분은 입력조건에서 다음 부분이다 다음 M개의 줄에는 숫자 v, w가 주어진다. 이것은 학생 v와 학생 w가 서로 친구라는 뜻이다. 자기 자신과 친구일 수도 있고, 같은 친구 관계가 여러 번 주어질 수도 있다. 크루스칼 알고리즘을 수행한후에 mst가 만들어졌는지 판단하는 방법은 최..