2020-09-17LeetCode13 minutes read (About 1906 words) 0 visits

LeetCode/684. 冗余连接

684. 冗余连接

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

输入一个图，该图由一个有着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是输入数组的大小。

来源：力扣（LeetCode）
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

判断路径中是否有环，在数据结构中我们学习过两种方法，即深度优先搜索遍历(DFS)和拓扑排序，在LeetCode上还有一种方法叫做并查集，我们一并介绍。

深度优先搜索遍历(DFS)

深度优先搜索遍历思想很简单，就是从某个结点开始不停地找相邻顶点，判断edges中的边的两个结点是否已经存在路径，如果存在，直接返回当前edge即我们要的结果。具体来说，就是将edges中每个edge的两个端点赋值给currNode和nextNode，我们去判断，能不能从currNode最终找到nextNode，如果能够找到，说明两端点之间已经存在一条路径，这时候，currNode和nextNode这条新的edge如果加入到graph中，那么一定会产生环，我们直接返回。

具体代码如下：

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        if (edges.length == 0) {
            return new int[]{};
        }
        //用来存放无向图
        Map<Integer, ArrayList<Integer>> graph = new HashMap<>();
        for (int[] edge : edges) {
            int currNode = edge[0];
            int nextNode = edge[1];
            //用于DFS标记当前结点有没有被访问
            boolean[] visited = new boolean[edges.length + 1];
            //查找currNode和nextNode之间是否有路径
            if (hasPath(currNode, nextNode, graph, visited)) {
                return edge;
            }

            //如果两个结点之间没有路径，则将两个结点加入到图中
            if (graph.get(currNode) == null) {
                graph.put(currNode, new ArrayList<>());
            }
            graph.get(currNode).add(nextNode);
            if (graph.get(nextNode) == null) {
                graph.put(nextNode, new ArrayList<>());
            }
            graph.get(nextNode).add(currNode);

        }
        return new int[]{};
    }

    private boolean hasPath(int currNode, int nextNode, Map<Integer, ArrayList<Integer>> graph, boolean[] vistied) {
        //说明currNode已经到nextNode，即currNode与nextNode存在路径
        if (currNode == nextNode) {
            return true;
        }
        vistied[currNode] = true;
        //当前两个结点都没有被访问过，则直接返回false
        if (!graph.containsKey(currNode) || !graph.containsKey(nextNode)) {
            return false;
        }
        ArrayList<Integer> neighbor = graph.get(currNode);
        for (Integer temp : neighbor) {
            //如果当前结点已经被访问过，则跳过访问下一个结点
            if (vistied[temp]) {
                continue;
            }
            if (hasPath(temp, nextNode, graph, vistied)) {
                return true;
            }
        }
        return false;
    }
}

由于采用深度优先搜索遍历，时间复杂度非常糟糕

拓扑排序

拓扑排序思想其实和广度优先搜索遍历大同小异，我们首先将edges中所有边加入图中，由于无向图不像有向图那样可以找到入度为0的起始点，我们只能搜索所有入度为1的结点，将它们加入队列当中。我们遵循这样的原则：首先从队列中弹出一个结点，找出与该结点相邻的所有结点，然后将这些结点的入度都减1，看看这些结点中有没有入度为1的结点，如果有，将它们入队，如此循环结束。我们寻找inCount数组中是否还有入度不为1的结点，这些结点对应的边就会形成环，我们逆序遍历，找到最后的那个成环的边返回即可。

具体代码如下：

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        if (edges.length == 0) {
            return new int[]{};
        }
        //用来存放无向图
        int[] inCount = new int[edges.length + 1];
        Map<Integer, ArrayList<Integer>> graph = new HashMap<>();
        for (int[] edge : edges) {
            int currNode = edge[0];
            int nextNode = edge[1];
            //入度自增一
            inCount[currNode]++;
            inCount[nextNode]++;

            //将两个结点加入到图关系中
            if (graph.get(currNode) == null) {
                graph.put(currNode, new ArrayList<>());
            }
            graph.get(currNode).add(nextNode);
            if (graph.get(nextNode) == null) {
                graph.put(nextNode, new ArrayList<>());
            }
            graph.get(nextNode).add(currNode);
        }

        //在无向图中，入度至少为1，我们遍历整个graph，将入度为1的结点加入队列
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i < edges.length + 1; i++) {
            if (inCount[i] == 1) {
                queue.add(i);
            }
        }

        //将队列中的元素出队，并将与之相邻的结点入度减1，如果相邻结点入度为1，则将该结点入队
        while (!queue.isEmpty()) {
            Integer temp = queue.poll();
            ArrayList<Integer> integers = graph.get(temp);
            for (Integer integer : integers) {
                if (--inCount[integer] == 1) {
                    queue.add(integer);
                }
            }
        }

        //如果遍历完后，inCount数组中还剩下入度大于1的元素，则这些元素对应的边就是环，我们逆序返回最后一个边即可
        for (int i = edges.length - 1; i > 0; i--) {
            if (inCount[edges[i][0]] > 1 && inCount[edges[i][1]] > 1) {
                return edges[i];
            }
        }
        return new int[]{};
    }
}

可以看到，采用拓扑排序，时间复杂度只是提高了一点点

并查集

并查集看过思想以后发现非常简单，并查集顾名思义有两个操作，即查找和合并，查找是查找当前元素的id，合并是指将两个有边连接的集合合并成一个集合，这里我们要把所有结点都与该集合的根结点直接相连，这样形成的树足够的平，保证能在O(1)的时间复杂度里面查找到我们想要的元素id。在本题中，查找即对应着查找当前结点的集合根结点是谁，合并即如果当前边所对应的两个结点不在同一集合，那么我们需要将这两个集合合并在一起。我们每次得到的u和v，需要判断当前两个结点是否处于同一集合当中，如果是，则加入这条边就会成环，我们需要返回这条边。

具体代码如下：

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        //存放当前结点父结点是哪个
        int[] parents = new int[edges.length + 1];
        //存放当前结点所在集合大小
        int[] sizes = new int[edges.length + 1];
        //默认每个森林只有一个结点的话，大小为1
        Arrays.fill(sizes, 1);

        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            //如果集合根结点为0，则将当前结点令集合为根结点
            if (parents[u] == 0) parents[u] = u;
            if (parents[v] == 0) parents[v] = v;

            //寻找u和v的根结点
            int pu = find(u, parents);
            int pv = find(v, parents);

            //如果父结点相等，添加这条边后会形成环
            if (pu == pv) return edge;

            //我们始终将小集合merge入大集合当中
            if (sizes[pv] > sizes[pu]) {
                int temp = pv;
                pv = pu;
                pu = temp;
            }

            parents[pv] = pu;
            sizes[pu] += sizes[pv];
        }
        return new int[]{};
    }

    int find(int target, int[] parents) {
        while (parents[target] != target) {
            //一次跳跃两个寻找当前结点的根结点
            parents[target] = parents[parents[target]];
            target = parents[target];
        }
        return target;
    }
}