작은 시작점

import java.util.Scanner;

public class Main {
	public static int T; // 테스트 케이스 개수
	public static int n, m; // 나라 n개, 비행기 m
	public static int[] parent = new int[1000001]; // 부모 테이블 초기화하기
    public static int result = 0;
    
    // 특정 원소가 속한 집합을 찾기
    public static int findParent(int x) {
        // 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
        if (x == parent[x]) return x;
        return parent[x] = findParent(parent[x]);
    }

    // 두 원소가 속한 집합을 합치기
    public static void unionParent(int a, int b) {
        a = findParent(a);
        b = findParent(b);
        if (a < b) parent[b] = a;
        else parent[a] = b;
    }

	public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        T = sc.nextInt();
        for (int t = 0; t < T; t++) {
            result = 0;
            n = sc.nextInt();
            m = sc.nextInt();
            
            // 부모 테이블상에서, 부모를 자기 자신으로 초기화
            for (int i = 1; i <= n; i++) {
                parent[i] = i;
            }
            
            for (int i = 0; i < m; i++) {
                int a = sc.nextInt();
                int b = sc.nextInt();
				
                if (findParent(a) != findParent(b)) {
                    unionParent(a, b);
                    result++;
                }
			}
            System.out.println(result);
		}
	}

}

상근이가 n개국을 여행할 때 m개의 비행기를 타고 이동해야하는데 가장 적은 비행기를 타야하니까 최소 간선의 개수를 구하면 된다.

가장 적은 종류의 비행기 == 최소 간선의 개수
1. 크루스칼 알고리즘으로 최소 신장 트리를 구한다.
2. 최소 신장 트리에 구성되어있는 간선의 개수가 최소 간선의 개수가 됨

T개의 테스트 개수만큼 반복해서 나라의 개수 n, 비행기의 개수 m을 구한다.

m번 a, b 쌍들을 입력 (a,b를 왕복하는 비행기)

a, b가 같은 집합에 속해있지 않을 때, 유니온 연산 실행(합집합을 만드는 연산) > 간선의 수 카운트 +1

만약 a, b가 같은 집합에 속해있다면, 유니온 연산을 실행하지 않음 -> 이미 이어지는 간선이 있다는 의미임 == 이어지는 비행기가 없어도 이동가능하다는 뜻 !

유니온 연산을 실행하는 것은 a, b가 이어지는 간선이 만들어진다는 의미이므로 비행기 종류의 최소 개수에 +1을 더함.

모든 연산이 끝나면 result 변수에 최소 간선의 수가 들어있게 된다.