Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
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
Value pair analysis
1(D).
To check whether a given number is smith number or not
Java messing around
메소드구현하기
Votes JAVA
rstring
Duplicate in string
Трикотаж
output2