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 ofedges. Each element ofedgesis a pair[u, v]withu < v, that represents an undirected edge connecting nodesuandv.

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, withu < 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

PreviousWord LadderNextRedundant Connection II

Last updated