Minimum Vertices to Traverse Directed Graph, Java

Minimum Vertices to Traverse Directed Graph

//'main' method must be in a class 'Rextester'.
//Compiler version 1.8.0_111

import java.util.*;
import java.lang.*;

class Rextester
{  
    public static void main(String args[])
    {
        //int[][] edges = {{2,9},{3,3},{3,5},{3,7},{4,8},{5,8},{6,6},{7,4},{8,7},{9,3},{9,6}};
        //int n = 10;
        // Test 2:
        // graph on page 10: https://web.stanford.edu/class/archive/cs/cs161/cs161.1138/lectures/04/Small04.pdf
        int[][] edges = {{0,3},{3,2},{2,0},{3,5},{5,6},{6,5},{5,9},{6,10},{9,10},{10,9},{1,4},{4,1},{4,6},{7,8},{4,7}};
        int n = 11;
        System.out.println(minSetToTraverse(edges, n).toString());
    }
    
    private static List<Integer> minSetToTraverse(int[][] edges, int n) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
        for (int[] edge: edges) graph.get(edge[0]).add(edge[1]);

List<Integer> order = new ArrayList<>();
        boolean[] visited = new boolean[n];
        for (int i = 0; i < n; i++) if (!visited[i]) DFS(graph, i, visited, order);
            
        Arrays.fill(visited, false);
        List<Integer> res = new ArrayList<>();
        for (int i = n - 1; i >= 0; i--) {
            if (!visited[order.get(i)]) {
                res.add(order.get(i));
                DFS(graph, order.get(i), visited, null);
            }
        }
        return res;
    }

private static void DFS(List<List<Integer>> graph, int start, boolean[] visited, List<Integer> order) {
        visited[start] = true;    
        for (int i: graph.get(start)) if (!visited[i]) DFS(graph, i, visited, order);
        if (order != null) order.add(start);
    }
}


run \| edit \| history \| help	0

λ

                                      .NET NoSQL database for rapid development