Two solutions - Disjoint Sets & DFS | Ruby
\nUnion find\ndef find_redundant_connection(edges)\n  @parent = Array.new(edges.size + 1, -1)\n  edges.each do |u, v|\n    return [u, v] if union(u, v)\n  end\n
```\nUnion find\ndef find_redundant_connection(edges)\n  @parent = Array.new(edges.size + 1, -1)\n  edges.each do |u, v|\n    return [u, v] if union(u, v)\n  end\nend\n\ndef union(u, v)\n  p1 = find(u)\n  p2 = find(v)\n  @parent[p2] = p1\n  p1 == p2\nend\n\ndef find(x)\n  return x if @parent[x] == -1\n  @parent[x] = find(@parent[x])\n  @parent[x]\nend\n\n```\n\n```\nDFS\ndef find_redundant_connection(edges)\n  @graph = {}\n  edges.each do |u, v|\n    return [u, v] if dfs(u, v, Set.new)\n    \n    @graph[u] = @graph[u] ? @graph[u].push(v) : [v]\n    @graph[v] = @graph[v] ? @graph[v].push(u) : [u]\n  end\nend\n\ndef dfs(u, v, visited)\n  visited.add(u)\n  if @graph[u]\n    return true if @graph[u].include?(v)\n    @graph[u].each do |neighbour|\n      unless visited.include?(neighbour)\n        visited.add(neighbour)\n        return true if dfs(neighbour, v, visited)\n      end\n    end\n  end\n  false\nend
['Depth-First Search', 'Union Find', 'Ruby']