백준 11724번 연결 요소의 개수_Union Find [JAVA]

11724번: 연결 요소의 개수

 

풀이 과정

방향 없는 그래프가 주어졌을 때, 연결 요소의 개수를 구하는 문제였습니다.

 

저는 Union Find 알고리즘을 이용하여 문제를 풀었으며,

각각의 간선의 부모(Find)가 다른 경우 Union 메서드를 통해 간선을 연결시켜 주었습니다.

 

M번의 반복문이 끝난 뒤, HashSet을 이용해 연결요소의 개수를 구해주었습니다.

 

[같은 문제의 배열 풀이방법]

백준 11724번 연결 요소의 개수 [JAVA]

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;
 
public class Main_BJ_11724_연결요소의개수 {
    
    static int N,M;
    static int [] parents;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        HashSet<Integer> hs = new HashSet<>();
        
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        parents = new int[N+1];
        
        for(int i=1;i<parents.length;i++) parents[i] = i;
        
        for(int i=0;i<M;i++) {
            st = new StringTokenizer(br.readLine());
            
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            
            if(find(u)!=find(v)) union(u,v);
                
        }
        
        for(int i=1;i<parents.length;i++) {
            hs.add(find(parents[i]));
        }
        
        System.out.println(hs.size());
    }
    
    public static void union(int a,int b) {
        int aRoot = find(a);
        int bRoot = find(b);
        
        if(aRoot>bRoot) parents[aRoot] = bRoot;
        else parents[bRoot] = aRoot;
    }
    
    public static int find(int a) {
        if(parents[a]==a) return a;
        return parents[a] = find(parents[a]);
    }
 
}