[알고리즘_풀이] 백준 11724, 연결 요소의 개수

문제의 예제입력 1번을 인접리스트(ArrayList)로 그린 것

// 방향 없는 그래프, 연결된 그래프 개수

import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;
import java.util.List;


public class Main {
    static boolean[] marked = null;
    static List<List<Integer>> none_direction_graph = null;
    //재귀호출
    static void dfs(int n){
        marked[n] = true;

        // 자식노드를 linkedNodeArr에 담는다.
        List<Integer> linkedNodeArr = none_direction_graph.get(n);

        for(int i=0; i<linkedNodeArr.size(); i++){
            if(!marked[linkedNodeArr.get(i)]) dfs(linkedNodeArr.get(i));
        }

    }

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

        int N = sc.nextInt();
        int M = sc.nextInt();

        none_direction_graph = new ArrayList<>();
        for(int i=0; i<=N; i++){
            none_direction_graph.add(new ArrayList<Integer>());
        }

        //input
        for(int i=0; i<M; i++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            none_direction_graph.get(a).add(b);
            none_direction_graph.get(b).add(a);
        }


        Stack<Integer> stack = new Stack<>();
        marked = new boolean[N+1]; //1~N 인덱스 사용

        int count = 0;
        for(int i=1; i<=N; i++){
            if(!marked[i]){
                count++;
                dfs(i);
            }
        }

        System.out.println(count);
    }
}

 

 

 

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

11724번: 연결 요소의 개수