Easy to understand AC solution


  • 0
    S

    Cost quite some time to make it AC. The basic idea (inspired from https://discuss.leetcode.com/topic/105087/share-my-solution-c ) is to check if there's a loop in graph, if the loop is there, it's very certain that the purpose is to break the loop and the answer (edge to be deleted) is there in loop; in the meantime, it can be concluded that those with more than two indegree should pick one of the incoming edge to delete, choose which one to delete depend on whether the edge is in a loop or not.
    In summary:
    1. if loop exists, break the loop
    1.1. pick last vertex on edge who has indegree value of 2, choose the edge on loop to remoe
    1.2. if no such vertex on loop exists, just pick the last edge in loop to remove
    2. if no loop , pick the last edges share the same "to" vertex

    vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
    
        unordered_map<int,int> in;
        unordered_map<int, vector<int>> g;
        
        int n = 0;
        for(auto& e: edges){
            in[e[1]]++;
            g[e[0]].push_back(e[1]);
            n = max(n, max(e[0], e[1]));
        }
        
        vector<bool> visited(n, false);
        // iterate to check loop existence
        for(int i = 1; i<= n; i ++){
            if (visited[n-1]){
                continue;
            }
            vector<int> path;
            unordered_set<int> circle ;
            unordered_map<int,int> posInPath;
            getCircle(g,i,posInPath, path, circle, visited);
            // if loop exists
            if (circle.size()){
                vector<int> lastEdgeInCircle = {};
    
                for(int i = edges.size()-1; i >= 0; i --){
                    auto e = edges[i];
                    if (circle.count(e[0]) && circle.count(e[1]) ){
                        if (lastEdgeInCircle.empty()){
                            lastEdgeInCircle = e;
                        }
    
                        //  last edge in loop with "to" vertex indegree value 2
                        if(in[e[1]] > 1){
                            // cout << "return here: multi parents, delete one" << endl;
                            return e;
                        }
                    }
                    
                }
                // else return the last edge on loop to break the circle
                return lastEdgeInCircle;
            }
        }
        // no loops there, remove the last edge with vertex indegree value of 2
        for(int i = edges.size()-1; i >= 0; i --){
            auto& e = edges[i];
            if(in[e[1]] > 1){
                return e;
            }
        }
        return {};        
    }
    

    // dfs to detect loop
    void getCircle(unordered_map<int, vector<int>>& g, int start, unordered_map<int,int>& posInPath, vector<int>& path, unordered_set<int>& res, vector<bool>& visited){
    if (posInPath.count(start)){
    res = unordered_set<int>(path.begin() + posInPath[start], path.end());
    return;
    }
    visited[start] = true;
    path.push_back(start);
    posInPath[start] = path.size()-1;
    for(auto& a: g[start]){
    getCircle(g, a, posInPath, path, res, visited);
    }
    posInPath.erase(start);
    path.pop_back();
    }


Log in to reply
 

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