Share my solution, C++


  • 13
    N

    This problem is limited to a graph with N nodes and N edges. No node is singled out if a edge is removed. For example, [[1,2],[2,4],[3,4]], 4 nodes 3 edges, is not applicable to this problem. You cannot remove [3,4] to single out node 3.

    There are 3 cases:

    1. No loop, but there is one node who has 2 parents.
    2. A loop, and there is one node who has 2 parents, that node must be inside the loop.
    3. A loop, and every node has only 1 parent.

    Case 1: e.g. [[1,2],[1,3],[2,3]] ,node 3 has 2 parents ([1,3] and [2,3]). Return the edge that occurs last that is, return [2,3].
    Case 2: e.g. [[1,2],[2,3],[3,1],[4,1]] , {1->2->3->1} is a loop, node 1 has 2 parents ([4,1] and [3,1]). Return the edge that is inside the loop, that is, return [3,1].
    Case 3: e.g. [[1,2],[2,3],[3,1],[1,4]] , {1->2->3->1} is a loop, you can remove any edge in a loop, the graph is still valid. Thus, return the one that occurs last, that is, return [3,1].

    class Solution {
    private:
        struct Node{
            vector<int> from; //parent(s), at most one node has 2 parents in a graph
            vector<int> to; //children, can have many children
        };
        unordered_map<int,Node> getNode;
        unordered_map<int,unordered_map<int,int>> edgeOrder;
        
    public:
        vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
            //construct the graph, and record the node which has 2 parents if possible
            int N = edges.size();
            for(int n=1; n<=N; ++n)
                getNode[n] = Node();
            int node2parents = -1;
            for(int i=0; i<N; ++i){
                int p = edges[i][0];
                int c = edges[i][1];
                edgeOrder[p][c] = i;
                getNode[p].to.push_back(c);
                getNode[c].from.push_back(p);
                if(getNode[c].from.size()==2) //we find a node with 2 parents
                    node2parents = c;
            }
            
            //doing DFS to find the loop if loop exists
            vector<int> status(N+1,0); // status 0,1,2 ==> 0:unvisited, 1:visiting, 2:visited
            stack<int> loop;
            bool loopfound = false;
            for(int i=1; i<=N; ++i){
                if(loopfound)   break;
                if(status[i] == 0){ //DFS started with node i
                    status[i] = 1;
                    stack<int> stk({i});
                    DFS(stk,status,loopfound,loop);
                    status[i] = 2;
                }
            }
            
            if(!loopfound){ // Case 1
                int parent1 = getNode[node2parents].from[0];
                int parent2 = getNode[node2parents].from[1];
                return (edgeOrder[parent1][node2parents] > edgeOrder[parent2][node2parents]) ?
                        vector<int>({parent1,node2parents}) : vector<int>({parent2,node2parents});
            }
            
            int last_occur_order = 0;
            vector<int> last_occur_edge;
            int begin = loop.top();
            while(!loop.empty()){
                int child = loop.top();
                loop.pop();
                int parent = loop.top();
                if(node2parents != -1 && child == node2parents) // Case 2
                    return vector<int>({parent,child});
                int order = edgeOrder[parent][child];
                if(order > last_occur_order){
                    last_occur_order = order;
                    last_occur_edge = vector<int>({parent,child});
                }
                if(parent == begin)
                    break; //loop ends
            }
            
            return last_occur_edge; // Case 3
        }
        
        void DFS(stack<int>& stk, vector<int>& status, bool& flag, stack<int>& loop){
            for(int c : getNode[stk.top()].to){
                if(flag)   return;
                if(status[c] == 1){
                    stk.push(c);
                    loop = stk;
                    flag = true;
                    return;
                }
                else if(status[c] == 0){
                    stk.push(c);
                    status[c] = 1;
                    DFS(stk,status,flag,loop);
                    status[c] = 2;
                    stk.pop();
                }
            }
        }
    };
    

  • 0
    J

    Your solution is correct, most of other answers posted based on union-find are wrong
    They just return the edge immediately if found that edge form a cycle or dup-parent. But it would fail on test cases like
    [[4,2],[1,5],[5,2],[5,3],[2,4]]
    and
    [[2,1],[3,1],[4,2],[1,4]]

    pls add these test cases
    @1337c0d3r


  • 0

    @JadenPan Thanks, I've just added both cases.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.