# 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 seeRedundant Connection II). We apologize for any inconvenience caused.

## Analysis & Solution

From 九章张老师

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

@李同学: 此题的思路比较简单, 就是不断地把边加入并查集中, 一旦发现有条边的两个端点已经在同一个集合内了, 证明这两个点之前已经连接过了, 那么目前的这条边就是多余的那条边

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