dfs and union find 
dfs \n\nclass Solution {\n    public int[] findRedundantConnection(int[][] edges) {\n      List<List<Integer>> adjList = new ArrayList<>();\n      for(int i = 0
dfs \n```\nclass Solution {\n    public int[] findRedundantConnection(int[][] edges) {\n      List<List<Integer>> adjList = new ArrayList<>();\n      for(int i = 0; i < edges.length + 1; i++){\n          adjList.add(new ArrayList<>());\n      }\n      for(int[] edge : edges){\n        int v = edge[0];\n        int u = edge[1];\n        \n        HashSet<Integer> visited = new HashSet<>();\n        \n        if(dfs(visited, u, v, adjList)){ // return true if there\'s a path between u and v already\n          // connect u and v directly make it a graph from tree\n          return edge;\n        }\n        // if the path doesnt exist \n        \n        adjList.get(u).add(v);\n        adjList.get(v).add(u);\n      }\n      return null;\n    }\n    private boolean dfs(HashSet<Integer> visited, int u, int v, List<List<Integer>> adjList){\n      // base case , when u and v are the same pos \n      if(u == v) return true;\n      \n      // else, mark u as visited\n      visited.add(u);\n      \n      \n      // check every nei, dfs on nei\n      for(int nei : adjList.get(u)){\n        if(visited.contains(nei)) continue;\n        if(dfs(visited, nei, v, adjList)) return true;\n      }\n      return false;\n    }\n}\n        \n```\nuf \n```\nclass Solution {\n    public int[] findRedundantConnection(int[][] edges) {\n      int n = edges.length;\n      UnionFind uf = new UnionFind(n);\n      \n      for(int[] edge : edges){\n        int u = edge[0];\n        int v = edge[1];\n        \n        if(uf.find(u) == uf.find(v)){\n          return edge;\n        }else{\n          uf.union(u, v);\n        }\n      }\n      return null;\n    }\n    \n    class UnionFind{\n      int[] parent;\n      \n      public UnionFind(int n){\n        parent = new int[n + 1];\n        for(int i = 1; i < n + 1; i++){\n          parent[i] = i;\n        }\n      }\n      \n      public void union(int a, int b){\n        int pa = find(a);\n        int pb = find(b);\n        parent[pa] = pb;\n      }\n      \n      public int find(int x){\n        while(parent[x] != x){\n          x = parent[x];\n        }\n        return x;\n      }\n    }\n\n}\n```
[]