백준 - 11724번(연결 요소의 개수)

문제 출처: https://www.acmicpc.net/problem/11724

문제

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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    private static List<Integer>[] adjList;
    private static boolean[] isVisited;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        int N = Integer.parseInt(tokenizer.nextToken());    // 정점의 개수
        int M = Integer.parseInt(tokenizer.nextToken());    // 간선의 개수

        adjList = new List[N + 1];
        for (int i = 0; i <= N; i++) {
            adjList[i] = new ArrayList<>();
        }

        for (int i = 0; i < M; i++) {
            tokenizer = new StringTokenizer(reader.readLine());
            int from = Integer.parseInt(tokenizer.nextToken()); // 점1
            int to = Integer.parseInt(tokenizer.nextToken());   // 점2

            // 무향 그래프이므로 양방향이다.
            adjList[from].add(to);
            adjList[to].add(from);
        }

        isVisited = new boolean[N + 1];   // 각 정점의 방문처리

        int cnt = 0;

        for (int i = 1; i <= N; i++) {
            if (!isVisited[i]) {
                cnt++;
                dfs(i);
            }
        }

        System.out.println(cnt);
    }

    private static void dfs(int n) {
        for (int x : adjList[n]) {
            if (!isVisited[x]) {
                isVisited[x] = true;
                dfs(x);
            }
        }
    }

}

• 연결 요소란, 하나의 정점에서 시작해서 연결되어 있는 모든 정점들 묶음을 연결 요소라 한다.
• DFS를 복습하는 느낌으로 문제를 풀었다. 인접 리스트를 만들어 연결되어 있는 모든 정점을 방문하면 되는 간단한 문제였다.