(11724) 연결 요소의 개수

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.

---

문제 풀이

해당 문제는 그래프 자료구조로 해결 할 수 있는 문제이다. 우선 인접리스트를 활용하여 문제를 풀어보려고 한다. 인접 리스트는 각 노드가 연결된 요소를 리스트로 입력받는 방식을 말한다. 

 

인접리스트로 표현하게 되면 아래와 같은 모습을 가지게된다. 

리스트에 입력 되는 예시를 하나를 들면 입력 값이 1 --> 2 를 이동한다고 했을 때 2에서도 1로 이동이 가능하므로 2의 List에도 1을 추가해주어야 한다. 

 

그렇게 만들어진 리스트를 그래프로 만들게 되면 아래와 같은 모습이다. 

총 두개의 그래프가 생성이 되므로 답은 2이다. 

---

나의 답안

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

public class Main {

    static List<Integer> graph[];
    static boolean[] visited;
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int e = sc.nextInt();

        graph = new ArrayList[n + 1];
        visited = new boolean[n + 1];

        for (int i = 0; i < n + 1; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int i = 0; i < e; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();

            graph[u].add(v);
            graph[v].add(u);
        }

        int cnt = 0;
        for (int i = 1; i < n + 1; i++) {
            if (!visited[i]){
                dfs(i);
                cnt++;
            }
        }

        System.out.println(cnt);

    }

    private static void dfs(int node) {
        visited[node] = true;

        for (int next : graph[node]) {
            if (!visited[next]) {
                dfs(next);
            }
        }
    }
}