Java dfs solution with explain
Since the question require us to remove the redundant edge, when we constructing the graph, we do dfs on each edge to see is it redundant, if yes return the edg
Since the question require us to remove the redundant edge, when we constructing the graph, we do dfs on each edge to see is it redundant, if yes return the edge, if no add the edge into the graph. \n\n\nWhy dfs can find redundant. Actually a redundant edge means after we add this edge, the graph will contain a cycle. So, when we came across a new edge, we do dfs from its start and its end, if there already exist a path from start to end, this new edge is redundant. \n\n```\n    boolean[] visited;\n\n    public int[] findRedundantConnection(int[][] edges) {\n        HashMap<Integer, List<Integer>> hashMap = new HashMap<Integer, List<Integer>>();\n        for(int i = 0; i < edges.length; i++){\n            hashMap.put(i + 1, new ArrayList<>());\n        }\n\n        int[] res = new int[2];\n        for(int i = 0; i < edges.length; i++){\n            int[] edge = edges[i];\n            visited = new boolean[edges.length + 1];\n            if(!hashMap.get(edge[0]).isEmpty() && !hashMap.get(edge[1]).isEmpty() && dfs(edge[0], edge[1], hashMap)){\n                return edge;\n            }\n            hashMap.get(edge[0]).add(edge[1]);\n            hashMap.get(edge[1]).add(edge[0]);\n        }\n        return res;\n    }\n\n    public boolean dfs(int src, int target, HashMap<Integer, List<Integer>> hashMap){\n        if(src == target){\n            return true;\n        }\n        visited[src] = true;\n        List<Integer> edgeList = hashMap.get(src);\n\n        for(Integer next: edgeList){\n            if(!visited[next]){\n                if(dfs(next, target, hashMap)){\n                    return true;\n                }\n            }\n        }\n\n        return false;\n    }\n```
['Depth-First Search', 'Java']