[백준] 9372 상근이의 여행(실버4) - 그래프

문제

코드

이 문제는 그래프를 탐색할 필요 없이 그래프의 기본 개념만 알고 있다면 쉽게 풀 수 있는 문제이다.
비행 스케줄을 항상 연결 그래프를 이룬다고 되어 있고 타야 하는 비행기의 종류를 구하라고 나와 있다. 이것을 그래프 용어로 바꾸어 설명하면 그래프는 연결 그래프이고 모든 노드를 지나는 간선의 최소 개수를 구하라는 뜻이고 간선의 최소 개수는 항상 N-1이므로(N: 노드의 수) N-1을 출력해주면 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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

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

        for (int i = 0; i < T; i++) {
            StringTokenizer st1 = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st1.nextToken());
            int M = Integer.parseInt(st1.nextToken());
            for (int j = 0; j < M; j++) {
                StringTokenizer st2 = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st2.nextToken());
                int b = Integer.parseInt(st2.nextToken());
            }
            System.out.println(N-1);
        }
    }
}