题目描述

在本问题中, 树指的是一个连通且无环的无向图。

输入一个图,该图由一个有着N个节点 (节点值不重复1, 2, …, N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间,这条附加的边不属于树中已存在的边。

结果图是一个以边组成的二维数组。每一个边的元素是一对[u, v] ,满足 u < v,表示连接顶点u 和v的无向图的边。

返回一条可以删去的边,使得结果图是一个有着N个节点的树。如果有多个答案,则返回二维数组中最后出现的边。答案边 [u, v] 应满足相同的格式 u < v。

示例 1:
输入: [[1,2], [1,3], [2,3]]
 输出: [2,3]
 解释: 给定的无向图为:
   1
  / \
 2 - 3
示例 2:
输入: [[1,2], [2,3], [3,4], [1,4], [1,5]]
输出: [1,4]
解释: 给定的无向图为:
 5 - 1 - 2
     |   |
     4 - 3
注意:
输入的二维数组大小在 3 到 1000。
二维数组中的整数在1到N之间,其中N是输入数组的大小。

更新(2017-09-26):
我们已经重新检查了问题描述及测试用例,明确图是无向图。
对于有向图详见冗余连接II。对于造成任何不便,我们深感歉意。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/redundant-connection
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解法1 – DFS

是的,这道题可以用DFS来做。我们创建一张没有边的空图G(V, E),然后从给定的边列表的顺序,一条一条地按照向图中添加边e(u, v)。但是在加边之前,用DFS判断能否从顶点u找到一条到达顶点v的路径,如果找不到这样的路径,那么就向图中添加边e(u, v);如果能找到一条从u到达v的路径,那我们再添加边e是不是就形成环路了?那这条边不就正是题目要求的答案吗?题目说的“如果有多个答案,则返回二维数组中最后出现的边”,其实就是指第一条使图包含环路的边。

为了实现算法,我们先要准备个数据结构存储图。我们可以用List<Integer>[N+1] graph来存储图,因为题目说了顶点最大编号为N,我们创建大小为N+1的数组,用顶点编号作为索引可以提升性能,当然你愿意用HashMap也可以。为了防止顶点的重复访问,我们需要用boolean[] visited[N+1]来记录已经访问过的顶点。

每添加一条边,我们都要判断之前已经添加过的边来判断u到v是否可达,所以时间复杂度为O(n^2);由于有visited数组开销O(|V|),调用栈开销O(|E|),所以空间复杂度为O(|V|+|E|)。全部代码如下:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        //二维数组中的整数在1到N之间,其中N是输入数组的大小
        int N = edges.length;
        List<Integer>[] graph = new List[N + 1];
        boolean[] visited = new boolean[N + 1];

        for (int[] edge : edges) {
            int src = edge[0];
            int dst = edge[1];

            if (canReach(src, dst, graph, visited))
                return edge;

            if (graph[src] == null)
                graph[src] = new ArrayList<>();
            if (graph[dst] == null)
                graph[dst] = new ArrayList<>();

            graph[src].add(dst);
            graph[dst].add(src);
            Arrays.fill(visited, false);
        }

        return null;
    }

    private boolean canReach(int src, int dst, List<Integer>[] graph, boolean[] visited) {
        visited[src] = true;

        if (graph[src] == null || graph[dst] == null)
            return false;

        if (src == dst)
            return true;

        for (int next : graph[src]) {
            if (!visited[next] && canReach(next, dst, graph, visited))
                return true;
        }

        return false;
    }
}

解法2 – Union-Find

Union-Find能够迅速地判断一对顶点是否处于同一个联通分量中,它看起来向一堆树的集合。顾名思义,Union-Find数据结构由Union和Find两个操作组成。Union操作用于将两个节点所在的树合并成一颗树,Find操作用于查找节点的祖先节点。我的描述可能不太严谨,具体可以参考教科书或者Wikipedia。

那回到题目上来,我们的解法1思路是用DFS判断添加一条边是否会使得图包含环路。但是解法1时间复杂度较高,我们换一种数据结构Union-Find能够快速地判断添加边是否会带来环路。我们在实现Union-Find时,进行了路径压缩和Rank合并优化,来降低Union-Find数据结构的深度。

均摊下来Union-Find的每个操作可以看作常数时间复杂度,因此总体时间复杂度为O(n),空间复杂度为O(n)。全部代码如下:

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        //二维数组中的整数在1到N之间,其中N是输入数组的大小
        int N = edges.length;

        int[] parent = new int[N + 1];
        int[] rank = new int[N + 1];

        // 一开始自己的parent都是自己
        for (int i = 0; i <= N; i++)
            parent[i] = i;


        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];


            // 两个节点的root相同,再继续添加边(u, v)就会形成环路,那么这条边就是答案
            if (!union(u, v, parent, rank))
                return edge;
        }

        return null;
    }

    private boolean union(int u, int v, int[] parent, int[] rank) {
        int rootU = find(u, parent);
        int rootV = find(v, parent);

        if (rootU == rootV)
            return false;

        // Union优化:将秩小的链接到秩大的节点上,以减小深度
        if (rank[rootU] < rank[rootV]) {
            parent[rootU] = rootV;
        } else if (rank[rootU] > rank[rootV]) {
            parent[rootV] = rootU;
        } else {
            parent[rootU] = rootV;
            rank[rootU]++;
        }

        return true;
    }

    private int find(int node, int[] parent) {
        // Union-Find优化:查找时进行路径压缩,以减小深度
        while (parent[node] != node) {
            parent[node] = parent[parent[node]];
            node = parent[node];
        }

        return node;
    }
}
pwrliang Algorithms, Cycle-Detection, DFS, Graph, Union-Find

Leave a Reply

Your email address will not be published. Required fields are marked *