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}}; 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
Java messing around
Геттеры и сеттеры для класса Dog
circleapp.java
Sort
Vasanth Selvaraj
BinaryTreeFindNext_noParentPointer
Consecutive Elements String
3
Elevator Sim
break