深さ優先探索(DFS)を再帰を用いて実装

有向グラフを想定した時の、DFSの使い方を整理しました。
ノード数nが与えられ、次に各ノードの出次数とそれぞれの隣接するノードをk個、入力された時に、どの順序でエッジを辿っていくかを出力するようにしています。

github.com

import java.util.Scanner;

public class DFS {

    static Scanner sc = new Scanner(System.in);
    static int n = sc.nextInt();
    static int[][] edge = new int[n][n];
    static boolean[] visited = new boolean[n];
    static int[] first_v = new int[n];  // 最初に訪れる時刻
    static int[] end_v = new int[n];    // 最後に訪れる時刻
    static int s = 0;

    public static void main(String[] args){

        for (int i=0; i<n; i++){
            int v = sc.nextInt()-1;
            int k = sc.nextInt();
            for (int j=0; j<k; j++){
                int u = sc.nextInt()-1;
                edge[v][u] = 1;
            }
        }
        dfs(0);
        for (int i=0; i<n; i++){
            System.out.println(first_v[i]);
        }
        System.out.println();
        for (int i=0; i<n; i++){
            System.out.println(end_v[i]);
        }
    }

    public static void dfs(int v){   // 再帰によるDFS

        first_v[v] = ++s;
        for (int u=0; u<n; u++){
            if (edge[v][u]==0) continue;
            if (!visited[u]){
                dfs(u);
            }
        }
        visited[v] = true;
        end_v[v] = ++s;
    }
}