<Algorithm> 29. 11724번 연결요소의 개수

1. 11724번 연결요소의 개수

• DFS 문제, 영역의 개수 구하는 문제와 동일한 방식

• 주의 할 점은 방향성이 없다는 것은 간선은 하나로 봐야하고 (1 3),(2 3) 이렇게 들어올떄 1-3-2 를 하나로 인식하는 지를 확인해야한다.  

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Main {
 
    static boolean[] visited;
    static int count;
    
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
    
        st = new StringTokenizer(br.readLine());
        
        int V = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        
        visited = new boolean[V];
        ArrayList<Edge>[] graph = new ArrayList[V];
        for(int i = 0; i < V; i++)
            graph[i] = new ArrayList<Edge>();
        
        
        for(int i = 0; i < M ; i++) {
            st = new StringTokenizer(br.readLine());
            int v = Integer.parseInt(st.nextToken())-1;
            int m = Integer.parseInt(st.nextToken())-1;
                graph[m].add(new Edge(v));                
                graph[v].add(new Edge(m));    // 방향성 제거
        }
        
        for(int i = 0; i < V ; i++) {
            if(!visited[i]) {
                dfs(i, graph);
                count++;
            }
        }
        System.out.println(count);
        
    }
    public static void dfs(int vertax, ArrayList<Edge>[] graph) {
                
        visited[vertax] = true;
        
        for(Edge e : graph[vertax]) {
            if(!visited[e.adjVertax]) {
                dfs(e.adjVertax, graph);
            }
        }
    }
    
}
 
class Edge{
    int adjVertax;
    public Edge(int adjVertax) {
        this.adjVertax = adjVertax;
    }
}