[BOJ] 14621번 나만 안되는 연애 (C++)

문제 (https://www.acmicpc.net/problem/14621)

14621번: 나만 안되는 연애

최소 스패닝 트리 문제이다. 크루스칼 알고리즘을 사용해서 해결했다.

특별히 어려운 점은 없는데 처리해야 할 조건이 하나 있다.

 

남초-남초, 여초-여초로 연결되면 안 되고 항상 번갈아가면서 연결되어야 한다. 따라서 나는 두 노드를 union 하기 전, 두 노드의 성별이 다른지 확인했다.

만약 해당 조건이 없다면 위 그래프의 답은 3(CD) + 5(BD) + 5(BE) + 10(AC) = 23이 될 것이다. 하지만 조건에 의해 오른쪽 사진과 같은 결과가 나온다.

 

만약 모든 학교를  연결하는 경로가 없을 경우 -1을 출력해야 한다. 두 노드가 union이 될 때마다 카운팅을 하여 카운트 수가 n - 1보다 작다면 -1을 출력하도록 했다.

---

[소스코드]

---

2022-03-03

Gold 3

- 그래프 이론

- 최소 스패닝 트리