You are viewing a single comment's thread. Return to all comments →
Java 8 with global variant using bfs
static int low = Integer.MAX_VALUE; static int findShortest(int graphNodes, int[] graphFrom, int[] graphTo, long[] ids, int val) { low = Integer.MAX_VALUE; List<Integer> colorList = new ArrayList<>(); for (int i = 0; i < ids.length; i++) { if(ids[i] == val) { colorList.add(i+1); } } Map<Integer, List<Integer>> dependecyList = new HashMap<>(); for (int i = 0; i < graphFrom.length; i++) { List<Integer> a1 = dependecyList.getOrDefault(graphFrom[i], new ArrayList<>()); a1.add(graphTo[i]); dependecyList.put(graphFrom[i], a1); List<Integer> a2 = dependecyList.getOrDefault(graphTo[i], new ArrayList<>()); a2.add(graphFrom[i]); dependecyList.put(graphTo[i], a2); } if(colorList.size() < 2) { return -1; } for (int i = 0; i < colorList.size(); i++) { bfs(colorList.get(i), val, ids, dependecyList); } return low; } static final void bfs(int start, int color, long[] ids, Map<Integer, List<Integer>> dependecyList) { Queue<Pair<Integer, Integer>> queue = new LinkedList<>(); Pair<Integer, Integer> pair = new Pair<>(start, 0); Set<Integer> vis = new HashSet<>(); vis.add(start); queue.offer(pair); while(!queue.isEmpty()) { Pair<Integer, Integer> pa = queue.poll(); Integer key = pa.getKey(); Integer count = pa.getValue(); List<Integer> li = dependecyList.get(key); if(li != null && !li.isEmpty()) { count++; for (Integer integer : li) { if(vis.contains(integer)) { continue; } if(ids[integer-1] == color) { low = Math.min(low, count); queue.clear(); break; } else { queue.offer(new Pair<>(integer, count)); } vis.add(integer); } } } }
Seems like cookies are disabled on this browser, please enable them to open this website
Find the nearest clone
You are viewing a single comment's thread. Return to all comments →
Java 8 with global variant using bfs