[Java] 백준 11724 : 연결 요소의 개수

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

1.

학교에서 자료구조 수업시간에 배운 내용이다.

시험 준비할 때 중요하다고 생각해서 공부해두었기에 생각이 났다.

(정○○ 교수님 수업 정말 알차게 열정적으로 해주셔서 감사합니다..)

 

 

2.

기본적인 DFS 탐색을 하되, 연결되지 않은 그래프는 한 번에 탐색되지 않는다.

따라서 방문하지 않은 노드를 찾아 DFS를 수행한다.

 

수업할 때 공부했던 자료를 참고하자.

 

 

3.

import java.util.Scanner;

public class Main {
    static int[][] graph;
    static boolean[] visited;

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);

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

        graph = new int[n + 1][n + 1];
        visited = new boolean[n + 1];
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();

            graph[u][v] = 1;
            graph[v][u] = 1;
        }

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

        System.out.println(cnt);
        sc.close();
    }

    static void dfs(int k, int n) {
        if (visited[k]) {
            return;
        }

        visited[k] = true;
        for (int i = 1; i <= n; i++) {
            if (graph[k][i] == 1) {
                dfs(i, n);
            }
        }
    }
}

 

 

4.

none