A simple C++ solution


  • 3
    X

    share my simple accepted solution:

    Thanks for indicating the problem with previous version. The revised version is given below.

    class Solution {
    public:
        bool validTree(int n, vector<pair<int, int>>& edges) {
            //use an array to record the root of each node
            vector<int> nodes(n, 0);
            for(int i = 0 ; i < nodes.size() ; i++){
                nodes[i] = i;
            }
            for(int i = 0; i < edges.size() ; i++){
                int root1 = edges[i].first;
                int root2 = edges[i].second;
                while(nodes[root1] != root1){
                    root1 = nodes[root1];
                }
                while(nodes[root2] != root2){
                    root2 = nodes[root2];
                }
                if(root1 == root2){
                    //if two nodes in the edge belong to same node, return false
                    return false;
                }
                nodes[root2] = root1;
            }
            return edges.size() == n-1;
        }
    };

  • 0
    W

    It is union-set like, but simpler


  • 0
    G

    I dont think it can handle the case such:
    4
    [[2,3],[1,2],[1,3]]


  • 0
    G

    Here's my improvement:

    class Solution {
    public:
        bool validTree(int n, vector<pair<int, int>>& edges) {
            vector<int> connect(n,0);
            vector<bool> visit(n,false);
            if(edges.size()!=n-1) return false;
            
            for(int i=0;i<n;i++){
                connect[i]=i;
            }
            for(int i=0;i<edges.size();i++){
                
                visit[edges[i].first]=visit[edges[i].second]=true;
                
                if(connect[edges[i].first]==connect[edges[i].second]) return false; //detect cycle
                
                connect[edges[i].second]=connect[edges[i].first];
            }
            for(int i=0;i<n-1;i++)
                if (!visit[i]) return false;
                
            return true;
        }
    };

  • 0
    X

    It still works wrong for the input n=5, [[2,3],[1,2],[1,3],[0,4]]


  • 0
    W

    5 [[0,1],[2,1],[2,0],[2,4]] is a similar failure case


  • 0
    X

    Thanks, you are right. A new version is given. Now the root of each node is derived before the judgement.


  • 0
    X

    Thanks for your indication. You are right. A new version is given to fix the bug.


  • 0
    X

    Thanks for the indication. A revised code is given to fix the bug in my answer.


Log in to reply
 

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