# Redundant Connection

`Tree`, `Union Find`, `Graph`

**Medium**

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

The given input is a graph that started as a tree with N nodes (with distinct values 1, 2, ..., 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 resulting graph is given as a 2D-array of`edges`. Each element of`edges`is a pair`[u, v]`with`u < v`, that represents an **undirected** edge connecting nodes`u`and`v`.

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 given 2D-array. The answer edge`[u, v]`should be in the same format, with`u < v`.

**Example 1:**

```
Input:
 [[1,2], [1,3], [2,3]]

Output:
 [2,3]

Explanation:
 The given undirected graph will be like this:
  1
 / \
2 - 3
```

**Example 2:**

```
Input:
 [[1,2], [2,3], [3,4], [1,4], [1,5]]

Output:
 [1,4]

Explanation:
 The given undirected graph will be like this:
5 - 1 - 2
    |   |
    4 - 3
```

**Note:**

The size of the input 2D-array will be between 3 and 1000.

Every integer represented in the 2D-array will be between 1 and N, where N is the size of the input array.

**Update (2017-09-26):**\
We have overhauled the problem description + test cases and specified clearly the graph is an **undirected** graph. For the **directed** graph follow up please see[**Redundant Connection II**](https://leetcode.com/problems/redundant-connection-ii/description/)). We apologize for any inconvenience caused.

## Analysis & Solution

From 九章[张老师](https://www.jiuzhang.com/solution/redundant-connection#tag-highlight)：

1. 首先思考使用暴力方式解决问题，我们穷举那条需要删除的边，然后都过深度优先搜索（dfs）验证删完之后的图是否为一棵树，时间复杂度是`O(n^2)`，虽然已经不错了，但这不是面试官预期的时间复杂度
2. 我们换个思路考虑，遍历所有边，一边遍历一边将当前边加入到图中。如果我们发现，有一条边\[u,v]还未曾加入到图中时，u和v就已经通过其他若干边相连，那么这就是我们要找的“多余”的边。
3. 如果我们还是用dfs去判断u和v的连通性，那么是`O(n)`的时间复杂度，总的时间复杂度仍是`O(n^2)`。这里我们就要用到一种数据结构叫做并查集，可以在常数时间内两个元素是否在同一集合（查询操作）和把两个元素合并到同一个集合（合并操作）。在并查集中，每个集合都有一个代表元素，我们称之为祖先。
4. 并查集的初始化：在最初的时候，根节点都是自己，我们用一个数组`parent[i]=i`来表示这个关系。
5. 并查集的查询操作：每次给边的时候判断两个点的祖先节点，我们不停地通过调用parent函数向上寻找直到`parent[i]==i`&#x20;
6. 给出一条边，两个节点设置为l ,r 如果祖先节点`father_l`, `father_r` 不相同，说明此时l和r不向连，这条边信息有用（不是一条多余的边），我们就通过并查集的合并操作将他们连在一起。具体操作需要将祖先节点接在一起，令`parent[father_r]=father_l`。
7. 路径压缩优化：在做查询操作的时候我们将`parent[now] = find_father(parent[now])`，是为了压缩路径，因为一旦两棵树合并，其中一些节点不是直接指向根节点的，不合并每次搜索会浪费大量时间
8. 我们认为总的时间复杂度是`O(n)`，其中使用了路径压缩的并查集的常数非常小可以忽略
9. 虽然题目强调如果有多个答案输出最后一条，但用上述方法只会找到一条“多余”的边，所以代码中是从前往后遍历所有边

**关于并查集：**

1. **并查集的初始化**：每次给边的时候判断两个点的根节点，在最初的时候，根节点都是自己，我们设一个数组`parent[i]=i`
2. 对于我们寻找父亲节点的时候，如果`parent[i]!=i` 代表着没有找到根节点，不停向上寻找
3. 给出一条边，两个节点设置为l ,r 如果根节点`father_l`, `father_r` 不相同，说明此时是两棵小树，这条边信息有用，将他们连在一起，也就是并查集的合并操作，具体操作需要将根亲节点接在一起，令`parent[father_r]=father_l`; 一旦parent和本身不相等，就说明向上还有根，这样便于我们判断是否在一棵树上
4. **路径压缩优化**：在dfs的时候我们将`parent[now] = find_father(parent[now])`，是为了压缩路径，因为一旦两棵树合并，其中一些节点不是直接指向根节点的，不合并每次搜索会浪费大量时间

### Union Find

> [@李同学](https://www.jiuzhang.com/solution/redundant-connection#tag-other): 此题的思路比较简单, 就是不断地把边加入并查集中, 一旦发现有条边的两个端点已经在同一个集合内了, 证明这两个点之前已经连接过了, 那么目前的这条边就是多余的那条边

```java
class Solution {
    class UnionFind {
        int[] parent;
        int[] rank;
        int size;

        public UnionFind(int size) {
            parent = new int[size];
            for (int i = 0; i < size; i++) {
                parent[i] = i;
            }
            rank = new int[size];
            this.size = size;
        }

        public int find(int x) {
            if (parent[x] != x) {
                 parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        public boolean union(int x, int y) {
            int xp = find(x);
            int yp = find(y);
            if (xp == yp) {
                return false;
            }
            if (rank[xp] < rank[yp]) {
                parent[xp] = yp;
            } else if (rank[xp] > rank[yp]) {
                parent[yp] = xp;
            } else {
                parent[yp] = xp;
                rank[xp]++;
            }

            return true;
        }
    }
    public int[] findRedundantConnection(int[][] edges) {
        //  int N = 1001;
        int N = edges.length;
        UnionFind uf = new UnionFind(N);
        for (int[] edge: edges) {
            if (!uf.union(edge[0] - 1, edge[1] - 1)) {
                return edge;
            }
        }
        return new int[0];
    }

}
```

## Reference

<https://www.jiuzhang.com/solution/redundant-connection#tag-highlight>