Easy C++ Solution 9ms


  • 0
    C

    Thanks to the samples of @niwota @wzypangpang, the solution has been updated.

    The unique redundant edge appears when

    1. an edge connect a child with its duplicated father.
    2. an edge which makes one and only one cycle in the tree.
    3. an edge such that both 1) and 2). (only one redundant edge)

    Solution:

    1. traverse each edge and record the edge which causes case 1) or 2);
    2. if case 1) doesn't occur, return the last input edge which makes a cycle under case 2).
    3. return the edge satisfying case 3) if it exists; otherwise, return the edge under case 1).
    class Solution {
    public:
        vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
            int u, v;
            bool hasCycle = false;
            vector<int> dup_node;  //{child, dup father}
            vector<int> ringEdge;
            for(const auto &e: edges){
                u = e[0]; v = e[1];
                //a node has multiple fathers
                if(fa.find(v) != fa.end()){
                    dup_node.push_back(v);
                    dup_node.push_back(u);
                }
                else fa[v] = u;
                //at most one cycle in the tree
                if(!hasCycle){
                    if(hasCycle = checkCycle(v)){
                        ringEdge.push_back(u);
                        ringEdge.push_back(v);
                    }
                }
            }
            if(dup_node.empty()) return ringEdge;
            if(checkCycle(dup_node[0])) return {fa[dup_node[0]], dup_node[0]};
            else return {dup_node[1], dup_node[0]};
        }
        bool checkCycle(int v){
            int node = v;
            while(fa.find(v) != fa.end()){
                v = fa[v];
                if(v == node) return true;
            }
            return false;
        }
        unordered_map<int, int> fa;
    };
    

  • 0
    N

    This solution is wrong.
    e.g. [[4,2],[1,5],[5,2],[5,3],[2,4]]
    Your answer [5,2]
    Expected answer [4,2]


  • 0
    W

    Can you try your solution on this test case:

    [[2,1],[3,1],[4,2],[1,4]]

    It seems your answer is [3,1] while expected answer is [2,1].

    Please correct me if I am wrong.


Log in to reply
 

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