LeetCode-685. 冗余连接 II

问题地址

LeetCode每日一题/2020-09-17

LeetCode685. 冗余连接 II

问题描述

规则

• 在本问题中，有根树指满足以下条件的有向图。该树只有一个根节点，所有其他节点都是该根节点的后继。每一个节点只有一个父节点，除了根节点没有父节点。
• 输入一个有向图，该图由一个有着N个节点 (节点值不重复1, 2, …, N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。
• 结果图是一个以边组成的二维数组。 每一个边 的元素是一对 [u, v]，用以表示有向图中连接顶点 u 和顶点 v 的边，其中 u 是 v 的一个父节点。
• 返回一条能删除的边，使得剩下的图是有N个节点的有根树。若有多个答案，返回最后出现在给定二维数组的答案。

示例

• 示例1

输入: [[1,2], [1,3], [2,3]]
输出: [2,3]
解释: 给定的有向图如下:
  1
 / \
v   v
2-->3

• 示例2

输入: [[1,2], [2,3], [3,4], [4,1], [1,5]]
输出: [4,1]
解释: 给定的有向图如下:
5 <- 1 -> 2
     ^    |
     |    v
     4 <- 3

备注

• 二维数组大小的在3到1000范围内。
• 二维数组中的每个整数在1到N之间，其中 N 是二维数组的大小。

解析

解题思路

数据操作分析

复杂度分析

编码实现

官方解法

方法一：并查集

思路：

• 在一棵树中，边的数量比节点的数量少 1。如果一棵树有 N 个节点，则这棵树有 N-1 条边。这道题中的图在树的基础上多了一条附加的边，因此边的数量也是 N。
• 树中的每个节点都有一个父节点，除了根节点没有父节点。在多了一条附加的边之后，可能有以下两种情况：
  • 附加的边指向根节点，则包括根节点在内的每个节点都有一个父节点，此时图中一定有环路；
  • 附加的边指向非根节点，则恰好有一个节点（即被附加的边指向的节点）有两个父节点，此时图中可能有环路也可能没有环路。
• 要找到附加的边，需要遍历图中的所有的边构建出一棵树，在构建树的过程中寻找导致冲突（即导致一个节点有两个父节点）的边以及导致环路出现的边。
• 具体做法是，使用数组 \textit{parent} 记录每个节点的父节点，初始时对于任何 1 \le i \le N 都有 \textit{parent}[i]=i，另外创建并查集，初始时并查集中的每个节点都是一个连通分支，该连通分支的根节点就是该节点本身。遍历每条边的过程中，维护导致冲突的边和导致环路出现的边，由于只有一条附加的边，因此最多有一条导致冲突的边和一条导致环路出现的边。
• 当访问到边 [u,v] 时，进行如下操作：
  • 如果此时已经有 \textit{parent}[v] \ne v，说明 v 有两个父节点，将当前的边 [u,v] 记为导致冲突的边；
    -否则，令 \textit{parent}[v] = u，然后在并查集中分别找到 u 和 v 的祖先（即各自的连通分支中的根节点），如果祖先相同，说明这条边导致环路出现，将当前的边 [u,v] 记为导致环路出现的边，如果祖先不同，则在并查集中将 u 和 v 进行合并。
• 根据上述操作，同一条边不可能同时被记为导致冲突的边和导致环路出现的边。如果访问到的边确实同时导致冲突和环路出现，则这条边被记为导致冲突的边。
• 在遍历图中的所有边之后，根据是否存在导致冲突的边和导致环路出现的边，得到附加的边。
• 如果没有导致冲突的边，说明附加的边一定导致环路出现，而且是在环路中的最后一条被访问到的边，因此附加的边即为导致环路出现的边。
• 如果有导致冲突的边，记这条边为 [u,v]，则有两条边指向 v，另一条边为 [\textit{parent}[v],v]，需要通过判断是否有导致环路的边决定哪条边是附加的边。
  -如果有导致环路的边，则附加的边不可能是 [u,v]（因为 [u,v] 已经被记为导致冲突的边，不可能被记为导致环路出现的边），因此附加的边是 [\textit{parent}[v],v]。
  • 如果没有导致环路的边，则附加的边是后被访问到的指向 v 的边，因此附加的边是 [u,v]。

复杂度分析

1. 时间复杂度：O(NlogN)。其中 N 是图中的节点个数。需要遍历图中的 N 条边，对于每条边，需要对两个节点查找祖先，如果两个节点的祖先不同则需要进行合并，需要进行 2 次查找和最多 1 次合并。一共需要进行 2N 次查找和最多 N 次合并，因此总时间复杂度是 O(2N \log N)=O(N \log N)。这里的并查集使用了路径压缩，但是没有使用按秩合并，最坏情况下的时间复杂度是 O(N \log N)，平均情况下的时间复杂度依然是 O(N \alpha (N))，其中 \alpha 为阿克曼函数的反函数，\alpha (N) 可以认为是一个很小的常数。

2.空间复杂度：O(N)。其中 N 是图中的节点个数。使用数组 \textit{parent} 记录每个节点的父节点，并查集使用数组记录每个节点的祖先。

编码实现

class Solution {
    public int[] findRedundantDirectedConnection(int[][] edges) {
        int nodesCount = edges.length;
        UnionFind uf = new UnionFind(nodesCount + 1);
        int[] parent = new int[nodesCount + 1];
        for (int i = 1; i <= nodesCount; ++i) {
            parent[i] = i;
        }
        int conflict = -1;
        int cycle = -1;
        for (int i = 0; i < nodesCount; ++i) {
            int[] edge = edges[i];
            int node1 = edge[0], node2 = edge[1];
            if (parent[node2] != node2) {
                conflict = i;
            } else {
                parent[node2] = node1;
                if (uf.find(node1) == uf.find(node2)) {
                    cycle = i;
                } else {
                    uf.union(node1, node2);
                }
            }
        }
        if (conflict < 0) {
            int[] redundant = {edges[cycle][0], edges[cycle][1]};
            return redundant;
        } else {
            int[] conflictEdge = edges[conflict];
            if (cycle >= 0) {
                int[] redundant = {parent[conflictEdge[1]], conflictEdge[1]};
                return redundant;
            } else {
                int[] redundant = {conflictEdge[0], conflictEdge[1]};
                return redundant;
            }
        }
    }
}

class UnionFind {
    int[] ancestor;

    public UnionFind(int n) {
        ancestor = new int[n];
        for (int i = 0; i < n; ++i) {
            ancestor[i] = i;
        }
    }

    public void union(int index1, int index2) {
        ancestor[find(index1)] = find(index2);
    }

    public int find(int index) {
        if (ancestor[index] != index) {
            ancestor[index] = find(ancestor[index]);
        }
        return ancestor[index];
    }
}

精彩评论

跳转地址1：685. 冗余连接 II:【并查集的应用】详解

思路

• 先重点读懂题目中的这句该图由一个有着N个节点 (节点值不重复1, 2, …, N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。
  • 这说明题目中的图原本是是一棵树，只不过在不增加节点的情况下多加了一条边！
• 还有若有多个答案，返回最后出现在给定二维数组的答案。这说明在两天边都可以删除的情况下，要删顺序靠后的！
• 那么有如下三种情况，前两种情况是出现入度为2的点，如图：
  
• 且只有一个节点入度为2，为什么不看出度呢，出度没有意义，一颗树中随便一个父节点就有多个出度。
• 第三种情况是没有入度为2的点，那么图中一定出现了有向环（注意这里强调是有向环！）如图：
  

算法分析

• 首先先计算节点的入度，代码如下：

        int inDegree[N] = {0}; // 记录节点入度
        n = edges.size(); // 边的数量
        for (int i = 0; i < n; i++) {
            inDegree[edges[i][1]]++; // 统计入度
        }

• 前两种入度为2的情况，一定是删除指向入度为2的节点的两条边其中的一条，如果删了一条，判断这个图是一个树，那么这条边就是答案，同时注意要从后向前遍历，因为如果两天边删哪一条都可以成为树，就删最后那一条。代码如下：

        vector<int> vec; // 记录入度为2的边（如果有的话就两条边）
        // 找入度为2的节点所对应的边，注意要倒叙，因为优先返回最后出现在二维数组中的答案
        for (int i = n - 1; i >= 0; i--) {
            if (inDegree[edges[i][1]] == 2) {
                vec.push_back(i);
            }
        }
        // 处理图中情况1 和 情况2
        // 如果有入度为2的节点，那么一定是两条边里删一个，看删哪个可以构成树
        if (vec.size() > 0) {
            if (isTreeAfterRemoveEdge(edges, vec[0])) {
                return edges[vec[0]];
            } else {
                return edges[vec[1]];
            }
        }

• 在来看情况三，明确没有入度为2的情况，那么一定有有向环，找到构成环的边就是要删除的边。可以定义一个函数，代码如下：

// 在有向图里找到删除的那条边，使其变成树，返回值就是要删除的边
vector<int> getRemoveEdge(const vector<vector<int>>& edges)

• 此时 大家应该知道了，我们要实现两个最为关键的函数：
  • isTreeAfterRemoveEdge() 判断删一个边之后是不是树了
  • getRemoveEdge 确定图中一定有了有向环，那么要找到需要删除的那条边
• 此时应该是用到并查集了，并查集为什么可以判断 一个图是不是树呢？
• 因为如果两个点所在的边在添加图之前如果就可以在并查集里找到了相同的根，那么这条边添加上之后 这个图一定不是树了

编码实现

class Solution {
private:
    static const int N = 1010; // 如题：二维数组大小的在3到1000范围内
    int father[N];
    int n; // 边的数量
    // 并查集初始化
    void init() {
        for (int i = 1; i <= n; ++i) {
            father[i] = i;
        }
    }
    // 并查集里寻根的过程
    int find(int u) {
        return u == father[u] ? u : father[u] = find(father[u]);
    }
    // 将v->u 这条边加入并查集
    void join(int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v) return ;
        father[v] = u;
    }
    // 判断 u 和 v是否找到同一个根
    bool same(int u, int v) {
        u = find(u);
        v = find(v);
        return u == v;
    }
    // 在有向图里找到删除的那条边，使其变成树
    vector<int> getRemoveEdge(const vector<vector<int>>& edges) {
        init(); // 初始化并查集
        for (int i = 0; i < n; i++) { // 遍历所有的边
            if (same(edges[i][0], edges[i][1])) { // 构成有向环了，就是要删除的边
                return edges[i];
            }
            join(edges[i][0], edges[i][1]);
        }
        return {};
    }

    // 删一条边之后判断是不是树
    bool isTreeAfterRemoveEdge(const vector<vector<int>>& edges, int deleteEdge) {
        init(); // 初始化并查集
        for (int i = 0; i < n; i++) {
            if (i == deleteEdge) continue;
            if (same(edges[i][0], edges[i][1])) { // 构成有向环了，一定不是树
                return false;
            }
            join(edges[i][0], edges[i][1]);
        }
        return true;
    }
public:

    vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
        int inDegree[N] = {0}; // 记录节点入度
        n = edges.size(); // 边的数量
        for (int i = 0; i < n; i++) {
            inDegree[edges[i][1]]++; // 统计入度
        }
        vector<int> vec; // 记录入度为2的边（如果有的话就两条边）
        // 找入度为2的节点所对应的边，注意要倒叙，因为优先返回最后出现在二维数组中的答案
        for (int i = n - 1; i >= 0; i--) {
            if (inDegree[edges[i][1]] == 2) {
                vec.push_back(i);
            }
        }
        // 处理图中情况1 和 情况2
        // 如果有入度为2的节点，那么一定是两条边里删一个，看删哪个可以构成树
        if (vec.size() > 0) {
            if (isTreeAfterRemoveEdge(edges, vec[0])) {
                return edges[vec[0]];
            } else {
                return edges[vec[1]];
            }
        }
        // 处理图中情况3
        // 明确没有入度为2的情况，那么一定有有向环，找到构成环的边返回就可以了
        return getRemoveEdge(edges);

    }
};

跳转地址2：【细致解读】一文让你真正读懂本题的思路

思路

• 当向一棵有向树插入一条额外的边 u \rightarrow v 时：
  • 一定会产生一个无向环
  • 另外，如果 v 并非树的根节点，则 v 会有两个不同的父节点。此时，我们称在节点 v 上产生了「冲突」，相关的两条边被称为「冲突边」。
• 由于我们仅插入了一条边，因此环与「冲突」的个数最多都只有一个。如果仅出现了环，我们需要将这个环「拆掉」；如果两者都出现，我们必须找到一条特殊的边，使得在「拆掉」环的同时，还能够将「冲突」解决。
• 如果出现了「冲突」，根据两条「冲突边」出现的位置，可以分成以下几种情况：
  • 两条边都在环外：不可能出现，否则不可能通过去掉一条边的方式，同时解决「环」和「冲突」。
  • 一条边在环外，一条边在环内：需要去掉在环内的那条边。
  • 两条边都在环内：去除其中一条即可。根据题意，我们要去除后出现的那条。
• 否则，如果只有「环」而没有「冲突」，则去除环中任意一条边即可。
• 判断一条特定的边是否在环内，是相对比较困难的事情。因此，我们采取一种比较巧的策略：如果发现了「冲突」边，就仅仅将后出现的那条记录下来，而不加到图中。通过这种方式，我们能够得到一张新图。如果原图中存在「冲突边」：
  • 对于一条边在环内，一条边在环外的情形：如果环内「冲突边」先出现，则新图中依然有环；否则，如果环外「冲突边」先出现，则由于随后不会将第二条在环内的「冲突边」加入到图中，因此新图中没有环。
  • 对于两条边都在环内：新图中一定没有环。
• 这样，不难发现：如果新图中有环，则要去除的是先出现的那条；否则，新图中如果没有环，则要去出的是后出现的那条。

算法

• 通过上面的分析，其实本题要解决的只有两个关键点：
  • 判断是否存在环：根据并查集，能够找到环中最后出现的那条边。
  • 判断是否存在「冲突」：判断是否有某个顶点 vv 有两条不同的入边。