DFS Java Solution With Explanation
Idea\nWe build adjList progressevily as we go on adding edges. Say we are trying to add the edge [u,v] and want to know if that will form a cyle. We do not add 
**Idea**\nWe build `adjList` progressevily as we go on adding edges. Say we are trying to add the edge `[u,v]` and want to know if that will form a cyle. We do not add the edge yet but we do `dfs` on the existing graph to see if we can reach `v` from `u`. If we can, then adding `[u,v]` will form a cycle. But we need the last possible edge that will form a cycle, so we can just set it to `ret` and move on without adding it.\n\nAlso since it is a `dfs` on an undirected graph, we have `v` in `u`\'s children and `u` in `v`\'s. So to avoid exploring the same edge from both the ends, we can pass in the current parent `pre` down the stack calls. \n\n```\npublic int[] findRedundantConnection(int[][] edges) {\n        int[] ret = null;\n        int n = edges.length;\n        List<Set<Integer>> adjList = new ArrayList<>(1001);\n        for(int i=0; i < 1001; i++)\n            adjList.add(new HashSet<>());\n        \n        for(int[] edge : edges){\n            int u = edge[0], v = edge[1];\n            if(dfs(u, v, 0, adjList)){\n                ret = edge;\n            }else{\n                adjList.get(u).add(v);\n                adjList.get(v).add(u);\n            }\n        }\n        return ret;\n    }\n    \n    private boolean dfs(int u, int v, int pre, List<Set<Integer>> adjList){\n        if(u == v)\n            return true;\n        for(int w : adjList.get(u)){\n            if(w == pre) continue;\n            boolean ret = dfs(w, v, u, adjList);\n            if(ret) return true;\n        }\n        return false;\n    }\n```
[]