백준 자바 :: 연결요소의 개수

 

 

 

import java.util.*;
import java.io.*;

public class Main {
    
    static ArrayList<Integer>[] A;
    static boolean[] visited ;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()); // 정점의 개수
        int m = Integer.parseInt(st.nextToken()); // 간선의 개수
        
        A = new ArrayList[n+1]; // 1부터 시작해서
        visited = new boolean[n+1];
        
        for(int i = 1; i < n+1; i++){
            A[i] = new ArrayList<Integer>();
        }
        
        for(int i = 0; i < m; i++){
            st = new StringTokenizer(br.readLine());
            int first = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            
            A[first].add(end);
            A[end].add(first);
        }
        
        int count = 0;
        
        for (int i = 1; i < n+1; i++){ // 1부터 시작
            if(!visited[i]){ // 방문하지 않은 노드가 있으면
                count++;
                DFS(i);
            }
        }
        
        System.out.println(count);
    }
    
    static void DFS(int node){
        // 현재노드와 방문노드가 같으면 return
        if(visited[node]){
            return;
        }
                
        // 현재 노드 방문 기록하기
        visited[node] = true;
        
        // 현재 노드의 연결 노드 중 방문하지 않은 노드로 DFS 실행
        for(int number : A[node]){
            if(!visited[number]){
                DFS(number);
            }
        }
    }
}