Cycle finding solution with Java


  • 0
    R
    public class Solution {
        public int[] findRedundantDirectedConnection(int[][] edges) {
            HashMap<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < edges.length; i++) {
                if (map.containsKey(edges[i][1])) {
                    if (findCycle(edges, i) == null) return edges[i];
                    return new int[] {map.get(edges[i][1]), edges[i][1]};
                } else {
                    map.put(edges[i][1], edges[i][0]);
                }
            }
            return findCycle(edges, -1);
        }
    
        int[] findCycle(int[][] edges, int ignore) {
            int[] parent = new int[1001];
            for (int i = 0; i < edges.length; i++) {
                if (i == ignore) continue;
                if (find(parent, edges[i][0]) == find(parent, edges[i][1])) return edges[i];
                parent[edges[i][1]] = edges[i][0];
    
            }
            return null;
        }
    
        int find(int[] parent, int child) {
            if (parent[child] == 0) {
                parent[child] = child;
            } else if (parent[child] != child) {
                parent[child] = find(parent, parent[child]);
            }
            return parent[child];
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.