문제

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

❓ 연결 요소란?
나누어진 각각의 그래프를 연결 요소라고 한다.


그림의 그래프의 연결 요소는 2개이다.

문제 풀이

1. 인접 행렬 + DFS 풀이

import java.io.*;

class Main{
    public static int count = 0; // 연결 요소의 수
    public static int[][] arr;   // 인접 행렬
    public static boolean[] visited;
    public static int E; // 정점 수
    public static int V; // 간선 수
    
    public static void main(String args[]) throws IOException {
        // 입력받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        E = Integer.parseInt(s[0]);
        V = Integer.parseInt(s[1]);

        // 인접 행렬 생성
        // 1부터 넣기 위해서 (e+1) x (e+1) 만큼의 2차원 배열을 생성한다.
        arr = new int[E+1][E+1];
        
        // visited 초기화
        visited = new boolean[E+1];

        for(int i=0;i<V;i++){
            s = br.readLine().split(" ");
            int e1 = Integer.parseInt(s[0]);
            int e2 = Integer.parseInt(s[1]);
            arr[e1][e2] = arr[e2][e1] = 1;
        }
        
        // DFS로 풀이
        // 모든 정점이 시작점이 된다.
        for(int i=1;i<=E;i++){
            if(visited[i] == false){
                // 한번 dfs를 돌고나면 count++
                dfs(i);
                count++;
            }
        }
        
        System.out.print(count);
    }
    
    public static void dfs(int start){
        visited[start] = true;
        
        // 더 이상 인접한 노드가 없거나 모두 들린 경우에 탈출
        for(int i=1;i<=E;i++){
            if(arr[start][i] == 1 && visited[i] == false){
                dfs(i);
            }
        }
    }
}

2. 인접 리스트 + DFS 풀이

[참고]
인접 행렬과 인접 리스트 - 1
인접 행렬과 인접 리스트 - 2
인접 리스트로 푼 경우
https://binghedev.tistory.com/5