알고리즘 수업 - 깊이 우선 탐색

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

24479번: 알고리즘 수업 - 깊이 우선 탐색 1

---

예제 케이스는 통과하는데 제출하면 틀리시는 분들을 위해 반례 드립니다.

 

1% ~ 3%                   70%

[입력]                         [입력]  

6 4 1                        5 1 3

2 3                           1 2

1 4

1 5

4 6

 

정답                             정답

1                                 0
0                                0
0                                1
2                                0
4                                0
3

 

---

 

 

[java]

 

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

public class Main {
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    static boolean visited[];
    static int depth[];
    static int cnt = 1;

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int m = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());
        int start = Integer.parseInt(st.nextToken());

        init(m,n,br,st);

        for(int i=0; i<graph.size(); i++)
            Collections.sort(graph.get(i));

        dfs(start);

        for(int i=1; i<=m; i++)
            System.out.println(depth[i]);


    }

    public static void dfs(int start){

        if(!visited[start]){
            visited[start] = true;
            depth[start] = cnt++;
            for(var num : graph.get(start)){
                if(!visited[num]){
                    dfs(num);
                }
            }
        }
    }

    public static void init(int m, int n, BufferedReader br, StringTokenizer st) throws IOException {
        visited = new boolean[m+1];
        depth = new int[m+1];
        for(int i=0; i<=m; i++) graph.add(new ArrayList<>());

        for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            graph.get(a).add(b);
            graph.get(b).add(a);
        }
    }

}