BOJ - 연결 요소의 개수 (11724)

https://www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

 

• 그래프를 탐색하며 연결 요소를 구하는 문제이다.
  • DFS 탐색 횟수를 카운팅하여 연결 요소를 개수를 구했다.
  • 그래프 기본 문제 유형인듯 

package baekjoon;

import java.lang.*;
import java.util.*;


public class Main {
    public static final Scanner scanner = new Scanner(System.in);

    public static final int NOT_VISITED = -1;

    public static void main(String[] args) throws Exception {
        int V = scanner.nextInt();
        int M = scanner.nextInt();

        ArrayList<Integer>[] adj = new ArrayList[V + 1];
        int[] visited = new int[V + 1];
        Arrays.fill(visited, NOT_VISITED);

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

        for (int i = 0; i < M; i += 1) {
            int u = scanner.nextInt();
            int v = scanner.nextInt();
            adj[u].add(v);
            adj[v].add(u);
        }

        Integer connected = 0;
        for (int i = 1; i <= V; i++) {
            if (visited[i] == NOT_VISITED) {
                connected += 1;
                dfsRecursive(i, connected, visited, adj);
            }
        }

        System.out.println(connected);
    }

    private static void dfsRecursive(int currentNode, Integer connected, int[] visited, ArrayList<Integer>[] adj) {
        visited[currentNode] = connected;
        for (int i = 0; i < adj[currentNode].size(); i++) {
            Integer next = adj[currentNode].get(i);
            if (visited[next] == NOT_VISITED) {
                dfsRecursive(next, connected, visited, adj);
            }
        }
    }
}