【leetcode】685. 冗余连接 II（redundant-connection-ii）（dfs）[困难]

链接

https://leetcode-cn.com/problems/redundant-connection-ii/

耗时

解题：1 h 51 min
题解：22 min

题意

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

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

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

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

思路

根据给出的边建图，并得到节点数 N，每个节点的入度。从后向前遍历给出的边，每次删除当前的边并更新入度，然后找是否有且只有一个节点的入度为 0，如果有多个节点入度为0或者没有节点入度为0则说明肯定不能删除当前边；而仅存在一个则说明这个节点可能是根节点，从它开始 dfs，如果 可以dfs到每个节点 说明这是个连通图即符合要求，直接返回当前边。否则把这条边补回去并回滚入度。

时间复杂度： O ( m N ) O(mN) O(mN) m 边的数量，N 节点的数量

AC代码

class Solution {
public:
    static const int MAXN = 1100;
    vector<int> E[MAXN];
    void add_edge(int u, int v) {
        E[u].push_back(v);
    }
    
    int vis_cnt = 0;
    
    void dfs(int s) {
        vis_cnt++;
        for(auto e : E[s]) {
            dfs(e);
        }
    }
    
    vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
        int in[MAXN] = {0};
        int num = 0;
        for(auto e : edges) {
            add_edge(e[0], e[1]);
            num = max(num, max(e[0], e[1]));
            in[e[1]]++;
        }        
        for(int t = edges.size()-1; t >= 0; t--) {
            auto e = edges[t];

            E[e[0]].erase(find(E[e[0]].begin(), E[e[0]].end(), e[1]));
            in[e[1]]--;
            
            int s = -1;
            for(int i = 1; i <= num; ++i) {
                if(in[i] == 0) {
                    if(s != -1) {
                        s = -1;
                        break;
                    }
                    s = i;
                }
            }
            if(s == -1) {
                add_edge(e[0], e[1]);
                in[e[1]]++;
                continue;
            }

            vis_cnt = 0;
            dfs(s);
            if(vis_cnt == num) return e;

            add_edge(e[0], e[1]);
            in[e[1]]++;
        }
        return {};
    }
};