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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/graph_search/redundant-connection.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.