상근이의 여행 9372

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

샘플예제를 직접 그려보면서 최소가 되는 경우를 어떻게 찾아야 하지 고민하다가 풀이를 보았다

"상근이가 가장 적은 종류의 비행기를 타고 모든 국가들을 여행할 수 있도록 도와주자"
"주어지는 비행 스케줄은 항상 연결 그래프를 이룬다"

저 문구들이 있다면 MST를 떠올리자

최소신장트리

import java.io.*;

public class Main
{
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());
        String[] input;
        for(int i = 0; i < T; ++i)
        {
            input = br.readLine().split(" ");
            int N = Integer.parseInt(input[0]);
            int M = Integer.parseInt(input[1]);

            System.out.println(N-1);
            
            for(int j = 0; j < M; ++j)
            {
               input = br.readLine().split(" ");
            }
        }
    }
}