C++, Union Find

  • 1

    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 {
        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);
        int root(vector<int>& parent, int k) {
            if (parent[k] != k) 
                parent[k] = root(parent, parent[k]); // path compression
            return parent[k];

  • 0

    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.