C++, Union Find


  • 1
    Z

    One of the test case is definitely not tree. I think the answer is to find acyclic connect graph, in which a node could have more than one parents.

    class Solution {
    public:
        vector<int> findRedundantConnection(vector<vector<int>>& edges) {
            vector<int> parent;
            for (int i = 0; i < 2001; i++) parent.push_back(i);
            for (auto edge:edges) { 
                int pa = root(parent, edge[0]), pb = root(parent, edge[1]);
                if (pa == pb) return edge; //already connected
                parent[pb] = pa;
            }
            return vector<int>(0, 0);
        }
    private:
        int root(vector<int>& parent, int k) {
            if (parent[k] != k) 
                parent[k] = root(parent, parent[k]); // path compression
            return parent[k];
        }
    };
    

  • 0
    S

    Get wrong answer.
    case: [[2,3],[5,3],[2,1],[5,4],[3,2]]


Log in to reply
 

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