[SW][union-find] 7465. 창용 마을 무리의 개수

7465. 창용 마을 무리의 개수

SW Expert Academy

 

• 내 풀이
  • union() 부분에서 int b= find(y) 한 후에 parent(b) 의값을 변경해줘야함!! 
    • parent(y) 하지 않도록 주의!

package day16_disjoint_set;

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

public class SW7465_ParkSomin {
    static int N,M, result;
    static int[] parent;

    public static void main(String[] args) throws IOException {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        int T= Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T ; tc++) {
            StringTokenizer st= new StringTokenizer(br.readLine());
            N=Integer.parseInt(st.nextToken());
            M=Integer.parseInt(st.nextToken());
            int result=0;
            parent=new int[N+1];
            for (int i = 0; i <= N; i++) {
                parent[i]=i;
            }

            for (int i = 0; i < M; i++) {
                st= new StringTokenizer(br.readLine());
                int a= Integer.parseInt(st.nextToken());
                int b= Integer.parseInt(st.nextToken());
                union(a,b);
            }

            for (int i = 1; i <= N; i++) {
                if (i==parent[i]) result++;
            }

            System.out.printf("#%d %d", tc,result);
            System.out.println();
        }


    }
    private static void union(int x, int y){
        int a= find(x);
        int b= find(y);
        //y의 부모가 아니라 b의 부모를 수정해줘야함.
        if (a!=b) parent[b]=a;
    }

    private static int find(int x){
        if(parent[x]!=x){
            parent[x]=find(parent[x]);
        }
        return parent[x];
    }
}