Run Code
|
API
|
Code Wall
|
Users
|
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}}; List<Integer> res = getMin(edges, 10); System.out.println(res); edges = new int[][]{{0, 0}, {1, 2}, {2, 0}, {2, 3}, {3, 1}}; res = getMin(edges, 4); System.out.println(res); assert 1 == res.size(); edges = new int[][]{{0, 1}, {1, 0}, {2, 1}, {2, 3}, {3, 2}}; res = getMin(edges, 4); System.out.println(res); assert 1 == res.size(); edges = new int[][]{{0, 1}, {1, 0}, {2, 1}, {3, 1}, {3, 2}}; res = getMin(edges, 4); System.out.println(res); assert 1 == res.size(); edges = new int[][]{{2, 9}, {3, 3}, {3, 5}, {3, 7}, {4, 8}, {5, 8}, {6, 6}, {7, 4}, {8, 7}, {9, 3}, {9, 6}}; res = getMin(edges, 10); System.out.println(res); assert 3 == res.size(); } private static void search(Set<Integer> res, Map<Integer, Set<Integer>> nodes, int cur, int start, Set<Integer> visited, Set<Integer> currVisited) { if(currVisited.contains(cur)) return; currVisited.add(cur); visited.add(cur); if(nodes.containsKey(cur)) { for(Integer edge : nodes.get(cur)) { if(edge != start && res.contains(edge)) res.remove(edge); search(res, nodes, edge, start, visited, currVisited); } } } private static List<Integer> getMin(int[][] edges, int n) { if(edges == null || edges.length == 0) return null; Map<Integer, Set<Integer>> g = new TreeMap<>(); for(int i = 0; i < n; i++) { g.put(i, new HashSet<>()); } for(int[] edge : edges) { g.get(edge[0]).add(edge[1]); } Set<Integer> visited = new HashSet<Integer>(); Set<Integer> res = new HashSet<Integer>(); for(int i = 0; i < n; i++) { if(!visited.contains(i)) { res.add(i); visited.add(i); search(res, g, i, i, visited, new HashSet<Integer>()); } } return new ArrayList<>(res); } }
run
|
edit
|
history
|
help
0
Please
log in
to post a comment.
Max Repeated Number in array
Strings Ops
Leetcode 202 Happy Number
Repeated Character Count In java
test1
final method
Selection Sort
상속2
jkbvlghckgh
l
Please log in to post a comment.