[코테 매일 풀기 5일차] 1029

백준 11724 연결 요소의 개수

아이디어

• union-find 알고리즘으로 root의 개수를 세자

//union -find로 루트 요소 개수 세기
public class Review2 {
    static int[] nodes;
    public static void main(String[] args) {
        //입력 받기
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int M = scan.nextInt();
        nodes = new int[N+1];
        for (int i =1; i <=N ; i++){
            nodes[i] = i;
        }//nodes
        for (int i = 0; i < M; i++){
            int a = scan.nextInt();
            int b = scan.nextInt();
            union(a, b); // union 연산
        }

//        //각 노드의 루트를 찾아 고유한 루트 개수 세기 => 안됨 : 정렬이 안되어 있기 때문에 중복 발생 
//        int cnt = 0;
//        for (int i = 1 ; i <N ; i++){
//            if (nodes[i] == nodes[i+1]){
//                cnt++;
//            }
//        }
        //System.out.println(cnt);

        // 최종 루트 찾는 방법
        Set<Integer> roots = new HashSet<>();
        for (int i = 1; i<=N; i++){
            roots.add(find(i));
        }
        System.out.println(roots.size());
    }
    
    //a,b 합집합 연산 
    static void union(int a, int b){
        int rootA = find(a); //a의 루트 노드 찾기
        int rootB = find(b); //b의 루트 노드 찾기
        if (rootA == rootB) return; //부모가 같으면 바로 return 
        nodes[rootB] = rootA; // 부모가 다르면, 다른 루트에 할당시킴 (합집합) 
    }
    //부모 찾기 
    static int find(int a){
        if (nodes[a] == a) return a; //자기 자신이 부모이면 자신 return 
        return nodes[a]= find(nodes[a]); //부모를 재귀적으로 찾음 
    }
}