0684. Redundant Connection

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

Description

In this problem, a tree is an undirected graph that is connected and has no cycles.

You are given a graph that started as a tree with n nodes labeled from 1 to n, with one additional edge added. The added edge has two different vertices chosen from 1 to n, and was not an edge that already existed. The graph is represented as an array edges of length n where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the graph.

Return an edge that can be removed so that the resulting graph is a tree of n nodes. If there are multiple answers, return the answer that occurs last in the input.

Example 1:

**Input:** edges = [[1,2],[1,3],[2,3]]
**Output:** [2,3]

Example 2:

**Input:** edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
**Output:** [1,4]

Constraints:

• n == edges.length

• 3 <= n <= 1000

• edges[i].length == 2

• 1 <= ai < bi <= edges.length

• ai != bi

• There are no repeated edges.

• The given graph is connected.

ac1: Union Find detect cycle

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        // edge cases

        // build union find
        int n = edges.length;
        int[] fathers = new int[n+1];
        for (int i = 0; i < fathers.length; i++) fathers[i] = i;

        // connect edges
        int[] res = new int[2];
        for (int[] e : edges) {
            int f1 = find(fathers, e[0]);
            int f2 = find(fathers, e[1]);
            if (f1 == f2) {
                res = e;
            } else {
                fathers[f1] = f2;
            }
        }

        return res;
    }

    private int find(int[] fathers, int i) {
        if (fathers[i] != i) {
            fathers[i] = find(fathers, fathers[i]);
        }
        return fathers[i];
    }
}
/*
UnionFind or Graph, when building if two vertice already processed before -> meet redundant edge
*/

ac2: DFS detect cycle

https://leetcode.com/problems/redundant-connection/discuss/277026/DFS-Java-Solution-With-Explanation

But with high time complexity.

public int[] findRedundantConnection(int[][] edges) {
        int[] ret = null;
        int n = edges.length;
        List<Set<Integer>> adjList = new ArrayList<>(1001);
        for(int i=0; i < 1001; i++)
            adjList.add(new HashSet<>());

        for(int[] edge : edges){
            int u = edge[0], v = edge[1];
            if(dfs(u, v, 0, adjList)){
                ret = edge;
            }else{
                adjList.get(u).add(v);
                adjList.get(v).add(u);
            }
        }
        return ret;
    }

    private boolean dfs(int u, int v, int pre, List<Set<Integer>> adjList){
        if(u == v)
            return true;
        for(int w : adjList.get(u)){
            if(w == pre) continue;
            boolean ret = dfs(w, v, u, adjList);
            if(ret) return true;
        }
        return false;
    }