困难

题目描述

在本问题中，有根树指满足以下条件的有向图。该树只有一个根节点，所有其他节点都是该根节点的后继。每一个节点只有一个父节点，除了根节点没有父节点。

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

结果图是一个以边组成的二维数组。每一个边的元素是一对 [u, v]，用以表示有向图中连接顶点 u 和顶点 v 的边，其中 u 是 v 的一个父节点。

返回一条能删除的边，使得剩下的图是有N个节点的有根树。若有多个答案，返回最后出现在给定二维数组的答案。

来源，leetcode 每日一题 685. 冗余连接 II

例如：

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

例如：

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

解题思路

若有入度为 22 的点，此点必有问题，答案在指向该点的边里
若都是入度为 11 的点，则有环，随意删一条都可断开环，但要保证被删的另一端还连在树上

代码

class Solution {
public:
    vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        // 出入度，邻接表
        vector<int> ins(n + 1), outs(n+1);
        vector<vector<bool>> adj(n+1, vector<bool>(n+1));
        vector<int> res;
        int tt = -1; // 记录入度为 2 的有问题的点，最多一个
        for (auto e : edges) {
            int from = e[0], to = e[1];
            ins[to]++;
            outs[from]++;
            adj[from][to] = true;
            // 入度为 2，该点有问题
            // 不急着处理，因还需遍历所有点，完善所有点出入度信息
            if (ins[to] == 2) tt = to;
            // 所有入度为 1，必成环，随便删哪个都能断开环
            // 删除最后一个、使入度点同时又有出度的那条边
            if (ins[to] == 1 && outs[to] > 0) res = e; 
        }
        if (tt != -1) {
            // 有入度为 2 的点
            res = vector<int>();
            // 找指向 tt 的边 && 来源点 f 又有出又有入——删此边不影响脱环
            for (int i = n - 1; i >= 0; i--) { // 逆序
                int f = edges[i][0], t = edges[i][1];
                if (t == tt && outs[f] + ins[f] > 1) {
                    // 只算最后一个
                    if (res.size()==0) res = edges[i];
                    // 相互指向则肯定有问题，如 [[4,2],[1,5],[5,2],[5,3],[2,4]]
                    if (adj[t][f]) return edges[i];
                }
            }
        }
        return res;
    }
};