[DFS] 백준 11724 연결 요소의 개수 JAVA

package com.test.dfs;

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

public class DFS_2_11724 {
    static int n;
    static int m;
    static ArrayList<Integer>[] arrayList; // 그래프 표현할 인접리스트
    static boolean[] visited; // 방문체크할 배열

    public static void main(String[] args) throws IOException {
        // [DFS] 백준 11724 연결 요소의 개수 JAVA
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]); // 정점의 개수
        m = Integer.parseInt(input[1]); // 간선의 개수

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

        for (int i = 0 ; i < m ; i++) {
            input = br.readLine().split(" ");
            int u = Integer.parseInt(input[0]);
            int v = Integer.parseInt(input[1]);

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

        int count = 0;
        for (int i = 1 ; i <= n ; i++) {
            if (!visited[i]) {
                dfs(i);
                count++;
            }
        }
        System.out.println(count);
    }
    private static void dfs(int node) {
        visited[node] = true;

        for (int x : arrayList[node]) {
            if (!visited[x]) {
                dfs(x);
            }
        }
    }
}

시간복잡도 : O(V+E), V:노드개수, E:간선개수