684.Redundant Connection

1-Union Find

261

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        Map<Integer, Integer> roots = new HashMap<>();
        for(int[] edge : edges){
            roots.put(edge[0], -1);
            roots.put(edge[1], -1);
        }
        int[] ans = new int[2];
        for(int[] edge : edges){
            int root1 = find(roots, edge[0]);
            int root2 = find(roots, edge[1]);
            if(root1 == root2){
                ans[0] = edge[0];
                ans[1] = edge[1];
                break;
            }
            else{
                roots.put(root1, root2);
            }
        }
        return ans;
    }
    public int find(Map<Integer, Integer> roots, Integer node){
        if(roots.get(node) == -1)
            return node;
        else{
            return find(roots, roots.get(node));
        }
    }
}

2-DFS

https://leetcode.com/problems/redundant-connection/solution/

When add edge to graph. For each edge(u, v), traverse the graph with a depth-first search to see if we can connect utov. If we can, then it must be the duplicate edge.