[BOJ][Python] 백준 14621번 - 나만 안되는 연애

문제 링크: https://www.acmicpc.net/problem/14621

14621번: 나만 안되는 연애

---

문제 풀이

최소 스패닝 트리를 이용하는 문제이다. 하지만 조건이 하나 추가 되었는데, 연결되어 있지 않은 간선을 유니온 시킬 때 둘다 남초 대학교 혹은 여초 대학교라면 유니온 시키지 않는다. 남자 - 여자 - 여자 - 남자 이렇게 연결 될 수도 있다 생각할 수 있는데 1번 조건에 따르면 불가능하다. 그 외에는 기본 최소 스패닝 트리이고 간선이 n-1개가 안된다면 -1을 출력해준다.

코드