[백준] 11724번 연결요소 구하기

문제 출처 

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

11724번: 연결 요소의 개수

 

 

 

접근 방식 및 풀이

- BFS, DFS 모두 가능하나 DFS를 이용하여 해결하였다. 

 

 

 

 

소스 코드 

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

public class Main {
    static boolean check[];
    static ArrayList<Integer>[] list ;
    static int node, edge, count;
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        node = sc.nextInt();
        edge = sc.nextInt();

        list = new ArrayList[node+1];
        check = new boolean[node+1];

        for (int i = 1; i <=node; i++) {
            list[i] = new ArrayList<>();
        }

        for (int j = 1; j <=edge ; j++) {
            int n = sc.nextInt();
            int e = sc.nextInt();

            list[n].add(e);
            list[e].add(n);
        }

        for (int i = 1; i <=node; i++) {
            if(!check[i]){
                count++;
                dfs(i);
            }
        }
        System.out.println(count);

    }

    private static void dfs(int x) {

        if(check[x]){
            return;
        }
        check[x] = true;
        for (int val: list[x]) {
            if(!check[val]){
                dfs(val);
            }
        }

    }



}

 

 

 

 

결과