20190205 11724번 : 연결 요소의 개수

연결 요소의 개수

링크

풀이

• 원래는 유니온 파인드를 생각했다.
• 하지만 문제의 유형은 DFS, BFS 를 말하고 있어서 DFS 로 방문배열을 설정해놓고 바로 해결할 수 있었다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
 
    static InputStreamReader isr;
    static BufferedReader br;
    static OutputStreamWriter osw;
    static BufferedWriter bw;
    static StringTokenizer st;
 
    static ArrayList<ArrayList<Integer>> list = null;
    static int[]visited = null;
    static int N = 0;
    static int M = 0;
    
    public static void main(String[] args) throws IOException {
 
        isr = new InputStreamReader(System.in);
        br = new BufferedReader(isr);
        osw = new OutputStreamWriter(System.out);
        bw = new BufferedWriter(osw);
        
        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        
        visited = new int[N + 1];
        Arrays.fill(visited, 0);
        
        list = new ArrayList<ArrayList<Integer>>();
        for(int i = 0; i <= N; i++) {
            list.add(new ArrayList<Integer>());
        }
        
        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            
            list.get(a).add(b);
            list.get(b).add(a);
        }
        
        int count = 0;
        for(int i = 1; i <= N; i++) {
            if(visited[i] == 1) {
                continue;
            }
            
            visited[i] = 1;
            count += 1;
            dfs(i);
        }
        
        bw.write(count + "\n");
        bw.flush();
        bw.close();
        br.close();
    }    
    
    private static void dfs(int start) {
        for(int i = 0; i < list.get(start).size(); i++) {
            int end = list.get(start).get(i);
            
            if(visited[end] == 1) {
                continue;
            }
            
            visited[end] = 1;
            dfs(end);
        }
    }
}