C++ iterative solution


  • 3
    J

    Build graph by input, use bfs to check every node's neighbor.
    If the neighbor is not parent and is visited, then there is a cycle, return false.
    Else put this neighbor in the queue.

    class Solution {
    public:
        struct node{
            int parent=0;
            vector<int>neighbors;
        };
        bool validTree(int n, vector<pair<int, int>>& edges) {
            unordered_map<int,node>nodes;
            if(edges.size()!=n-1)return false;
            vector<bool>v(n,false);
            for(auto edge:edges){
                nodes[edge.first].neighbors.push_back(edge.second);
                nodes[edge.second].neighbors.push_back(edge.first);
            }
            queue<int>q;
            q.push(0);
            v[0]=true;
            while(!q.empty()){
                int p=q.front();
                q.pop();
                for(auto n:nodes[p].neighbors){
                    if(n!=nodes[p].parent){
                        if(v[n])return false;
                         v[n]=true;
                         nodes[n].parent=p;
                         q.push(n);
                    }
                }
            }
            return true;
        }
    };

  • 0

    A great solution! But I think it is BFS instead of DFS. Note that you keep all the nodes in the same level in a queue.


  • 0
    J

    Yea, you are right, I am wrong. It is BFS. Thanks for the correction.


  • 0
    R

    Your code gives a wrong answer in a few cases. You have not checked connected properly. You need the following

    for (int i=0; i<n; i++)
    if (!v[i]) return false;


  • 0
    R

    And since the nodes are from [0,n), I can just use vector<int> and do not need a struct node. The following is accepted version.

    class Solution {
    public:
    
        bool validTree(int n, vector<pair<int, int>>& edges) {
            if(edges.size()!=n-1) return false;
            vector<vector<int>> neighbors (n, vector<int> ());
            for (int i=0; i<edges.size(); i++) {
                neighbors[edges[i].first].push_back(edges[i].second);
                neighbors[edges[i].second].push_back(edges[i].first);
            }
            vector<int> childparent (n,0);
            vector<int> visited  (n, false);
            queue<int> Q;
            Q.push(0);visited[0]=true;
            
            while (!Q.empty()) {
                int p = Q.front();
                Q.pop();
                for (int i=0; i<neighbors[p].size(); i++) {
                    if (childparent[p]!= neighbors[p][i]) {
                        if ( visited[neighbors[p][i]]) return false;
                        Q.push(neighbors[p][i]);
                        visited[neighbors[p][i]] = true;
                        childparent[neighbors[p][i]] = p;
                    }
                }
            }
             for (int i=0; i<n; i++)
                if (!visited[i]) return false;
            return true;
            
        }
    };

Log in to reply
 

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