알고리즘 분류에 최소 스패닝 트리라고 되어있는 힌트를 보고 유추해서 겨우 풀었는데,

문제를 읽어보면 모든 도시들이 같은 집합에 존재한다는 말이 없지 않나요? 

해당 말이 문제에 없어 모든 도시들이 같은 집합에 속해있지 않더라도 M개가 연결돼있기만 하면 된다고 인식했었습니다.

혹시 제가 모든 도시들이 같은 집합 내에 속해있다는 조건이 문제 속에 있고 MST 로 풀릴 수 있음을 보장하는데 제가 못보고 있는거라면 알려주실 수 있는 고수분이 계실까요?

감사합니다.