Short solutions, finding nodes' parent


  • 0
    C

    Inputs guarantee only one edge needs to be removed to make the directed graph a tree, so there are only two cases where an edge needs to be deleted:

    1. An edge that makes a node having more than one parents;
    2. An edge that cause a loop.

    For each edge (u -> v), we firstly check whether the child (v) has already had a parent. If not, only an edge that connect the root and its descendent can make a loop. So we only need to check whether v is u's root.

    C++:

    vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
        unordered_map<int, int> parents;   // record tree nodes and its parents
        for (int i = 0; i < edges.size(); i++) {
            if (parents.find(edges[i][1]) != parents.end()) return edges[i]; //more than one parents
            int p = edges[i][0];   // finding u's root
            while (parents.find(p) != parents.end()) p = parents[p];
            if (p == edges[i][1]) return edges[i];
            parents[edges[i][1]] = edges[i][0];
        }
        return {};
    }
    

    Python:

    def findRedundantDirectedConnection(self, edges):
        parents = {}
        for e in edges:
            if e[1] in parents: return e
            p = e[0]
            while p in parents: p = parents[p]
            if p == e[1]: return e
            parents[e[1]] = e[0]
        return []
        
    

  • 0

    This code fails at:
    Input:
    [[2,1],[3,1],[4,2],[1,4]]
    Output:
    [3,1]
    Expected:
    [2,1]


Log in to reply
 

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