> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/0684-redundant-connection.md).

# 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:**

![](https://assets.leetcode.com/uploads/2021/05/02/reduntant1-1-graph.jpg)

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

**Example 2:**

![](https://assets.leetcode.com/uploads/2021/05/02/reduntant1-2-graph.jpg)

```
**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

```java
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.

```java
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;
    }
```