685

685. Redundant Connection II (Hard)

In this problem, a rooted tree is a directed graph such that, there is exactly one node (the root) for which all other nodes are descendants of this node, plus every node has exactly one parent, except for the root node which has no parents.

The given input is a directed graph that started as a rooted tree with n nodes (with distinct values from 1 to n), with one additional directed edge added. The added edge has two different vertices chosen from 1 to n, and was not an edge that already existed.

The resulting graph is given as a 2D-array of edges. Each element of edges is a pair [ui, vi] that represents a directed edge connecting nodes ui and vi, where ui is a parent of child vi.

Return an edge that can be removed so that the resulting graph is a rooted tree of n nodes. If there are multiple answers, return the answer that occurs last in the given 2D-array.

 

Example 1:

Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]

Example 2:

Input: edges = [[1,2],[2,3],[3,4],[4,1],[1,5]]
Output: [4,1]

 

Constraints:

• n == edges.length
• 3 <= n <= 1000
• edges[i].length == 2
• 1 <= ui, vi <= n
• ui != vi

Companies:
Amazon

Related Topics:
Depth-First Search, Breadth-First Search, Union Find, Graph

Similar Questions:

• Redundant Connection (Medium)

Solution 1.

If a node has indegree 2:

• If there is a cycle in the graph, delete the edge pointing to this node within the cycle. (case 1)
• If there is no cycle, delete the edge with greater index. (case 2) Otherwise there must be a cycle in the graph, delete an edge in the cycle with the greatest index (case 3)

NOTE: this solution is too complicated. Need to find better solution in Discuss.

// OJ: https://leetcode.com/problems/redundant-connection-ii/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
    vector<int> findRedundantDirectedConnection(vector<vector<int>>& E) {
        int N = E.size(), terminal = -1;
        vector<vector<pair<int, int>>> G(N);
        vector<vector<pair<int, int>>> R(N);
        vector<bool> onCycle(N, true);
        vector<int> indegree(N), outdegree(N);
        for (int i = 0; i < N; ++i) {
            int u = E[i][0] - 1, v = E[i][1] - 1;
            G[u].push_back({v,i});
            R[v].push_back({u,i});
            if (++indegree[v] == 2) terminal = v;
            ++outdegree[u];
        }
        auto hasCycle = [&]() { // Topological sort to see if there is any cycle in the graph
            queue<int> q;
            int seen = 0;
            for (int i = 0; i < N; ++i) {
                if (indegree[i] == 0) q.push(i);
            }
            while (q.size()) {
                int u = q.front();
                onCycle[u] = false;
                ++seen;
                q.pop();
                for (auto &[v, i] : G[u]) {
                    if (--indegree[v] == 0) q.push(v);
                }
            }
            return seen < N;
        };
        if (hasCycle()) {
            if (terminal != -1) { // case 1
                int a = R[terminal][0].first, b = R[terminal][1].first;
                if (onCycle[a]) return {a + 1, terminal + 1};
                return {b + 1, terminal + 1};
            }
            queue<int> q; // case 3
            for (int i = 0; i < N; ++i) {
                if (outdegree[i] == 0) q.push(i);
            }
            while (q.size()) {
                int u = q.front();
                q.pop();
                onCycle[u] = false; // Topological Sort on the reversed graph to remove nodes that are not on the cycle.
                for (auto &[v, i] : R[u]) {
                    if (--outdegree[v] == 0) q.push(v);
                }
            }
            int ans = -1;
            for (int i = 0; i < N; ++i) {
                if (!onCycle[i]) continue;
                for (auto &[v, j] : R[i]) {
                    ans = max(ans, j); // Find the greatest edge index on the cycle
                }
            }
            return E[ans];
        }
        return {R[terminal][1].first + 1, terminal + 1}; // case 2
    }
};