백준 9372번 상근이의 여행 JAVA

링크텍스트

설명

모든 나라를 여행한다는 것은 그래프의 모든 정점을 연결하는 최소 간선 집합을 선택하는 것과 같음.
최소 스패닝 트리(MST) 문제와 같음.
연결 그래프에서 모든 정점을 여행하는 최소 간선 수 = N - 1임.
왜냐하면 최소 스패닝 트리(MST)는 항상 N-1개의 간선으로 N개의 노드를 연결하기 때문.
문제에서 비행기 종류가 여러 개 있든, 종류와 관계없이 그냥 간선 수만 세면 됨.
예제에서
3개 나라 → 최소 비행기 종류 = 2
5개 나라 → 최소 비행기 종류 = 4
즉 항상 N - 1을 출력하면 되는 문제이다.
시간복잡도: O(N), 공간복잡도: O(1)

회독

• [ x ] 1회
• 2회
• 3회

코드

import java.io.*;
import java.util.*;

public class Main {
        static int n,m;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int t = Integer.parseInt(br.readLine());

        while(t-->0){
            st = new StringTokenizer(br.readLine());

            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());

            for(int i=0;i<m;i++){
                st = new StringTokenizer(br.readLine());

                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
            }
            sb.append(n-1).append("\n");
        }

        System.out.print(sb);
    }
}