Strange result: Input: [[1,2],[2,3],[3,4],[1,4],[1,5]] Output: [] Expected: [3,1]


  • 0
    X

    Find my C++ code below. The result of submit solution and Run code is totally different:

    Run Code Result:×

    Your input

    [[1,2],[2,3],[3,4],[1,4],[1,5]]
    Your answer

    [1,4]
    Expected answer

    [1,4]


    Code

        vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        
        int N = 0;
        for (auto edge : edges)
        {
            N = max(edge[0],N);
            N = max(edge[1],N);
        }
        
        vector<unordered_set<int>> graph(N+1, unordered_set<int>());
    
        for (auto edge : edges)
        {
            int first = edge[0];
            int second = edge[1];
            // (graph[first].find(second) != graph[first].end() && graph[second].find(first) != graph[second].end())
            //    return edge;
    
            graph[first].insert(second);
            graph[second].insert(first);
        }
    
        unordered_set<int> loop;
        queue<int> q;
        for (int i = 1; i <= N; ++i)
        {
            if (graph[i].size() == 1)
                q.push(i);
        }
    
        while (!q.empty())
        {
            int num = q.size();
    
            for (int i = 0; i < num; ++i)
            {
                int curr = q.front();
                q.pop();
    
                unordered_set<int> nexts;
                for (auto next : graph[curr])
                {
                    graph[next].erase(curr);
                    nexts.insert(next);
                 }
    
                for (auto next : nexts)
                {
                    if (graph[next].size() == 1)
                        q.push(next);
                }
                graph[curr].clear();
            }
        }
    
        for (int i = 1; i <= N; ++i)
        {
            if (graph[i].empty()) continue;
            loop.insert(i);
        }
        if (loop.empty() )
            return vector<int>();
        
        int len = edges.size();
        for ( int i = len-1; i >=0; --i )
        {
            int first = edges[i][0];
            int second = edges[i][1];
            if (loop.find(second) != loop.end() && loop.find(first) != loop.end())
                return edges[i];
        }
    
        return vector<int>();        
        }
    

Log in to reply
 

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