16-lines C++ DFS


  • 11

    As suggested by the hint, just check for cycle and connectedness in the graph. Both of these can be done via DFS.

    The code is as follows.

    class Solution {
    public:
        bool validTree(int n, vector<pair<int, int>>& edges) {
            vector<vector<int>> neighbors(n);
            for (auto e : edges) {
                neighbors[e.first].push_back(e.second);
                neighbors[e.second].push_back(e.first);
            }
            vector<bool> visited(n, false);
            if (hasCycle(neighbors, 0, -1, visited))
                return false;
            for (bool v : visited)
                if (!v) return false; 
            return true;
        } 
    private:
        bool hasCycle(vector<vector<int>>& neighbors, int kid, int parent, vector<bool>& visited) {
            if (visited[kid]) return true;
            visited[kid] = true;
            for (auto neigh : neighbors[kid])
                if (neigh != parent && hasCycle(neighbors, neigh, kid, visited))
                    return true;
            return false;
        }
    };

  • 0
    K

    The idea of onpath is terrific!!!


  • 0
    S

    Can use unordered_set<int> for visited and just check if visited.size() == n, instead of loop


  • 0
    Z

    Is there a specific reason for keeping two different arrays for "onpath" and "visited"? I think if we have finished DFS on one path, there is no way to visit nodes on this path from nodes on other paths, or it would not be a tree...


  • 1
    W

    Hi , jianchao, I think vector<bool>onpath has no use. Here is my cpp code, same idea :-)

    class Solution {
    public:
        bool validTree(int n, vector<pair<int, int>>& edges) {
        vector<vector<int>> edgelists(n);
        for(auto i:edges)
        {
            edgelists[i.first].push_back(i.second);
            edgelists[i.second].push_back(i.first);
        }
        vector<bool> visited(n,false);
        if(hascycle(edgelists,visited,0,-1)) return false;
        for(auto i:visited)
            if(!i) return false;
        return true;
        }
        
        bool hascycle(vector<vector<int>> &edgelists,vector<bool> &visited,int cur,int parent)
        {
            if(visited[cur]) return true;
            visited[cur]=true;
            for(auto kid:edgelists[cur])
                if(kid!=parent&&hascycle(edgelists,visited,kid,cur))
                    return true;
            return false;
        }
    };

  • 1

    Hi, wei_fy. Great thanks for your suggestions and code! I have updated my post now.


  • 0

    @smileyogurt.966 Yeah, you're right. I do not remember why I use vector at that time (possibly maybe it runs even faster than unordered_set version in practice).


  • 0

    @zimu.li Thanks! I have updated my post now.


  • 6
    X

    Hi @jianchao.li.fighter, really appreciate your post.

    However, I think maybe we don't have to check if there is a cycle in the graph through the dfs recursion.

    Think about the number of edges, if there is n-1 edges total, and we can go through every node using bfs starting from one node, it means that the graph is connected and cannot have any cycle.

    Here is my renewed code :)

    class Solution {
    public:
        bool validTree(int n, vector<pair<int, int>>& edges) {
            if(edges.size() != n-1) return false;
            vector<vector<int>> graph(n);
            for(auto e : edges){
                graph[e.first].push_back(e.second);
                graph[e.second].push_back(e.first);
            }
            vector<bool> isVisited(n, false);
            dfs(graph, isVisited, 0);
            bool ret = true;
            for(int i=0; i<n; i++) ret &= isVisited[i];
            return ret;
        }
    private:
        void dfs(vector<vector<int>> &graph, vector<bool> &isVisited, int node){
            if(isVisited[node]) return;
            isVisited[node] = true;
            for(int neigh : graph[node]){
                dfs(graph, isVisited, neigh);
            }
        }
    };
    

  • 0

    Hi, xuweineo2. Good code using the idea that the number of edges must be n - 1 to be a valid tree! Thanks for your sharing :-)


  • 0
    M

    @jianchao-li-fighter
    Hello! my solution shares the same idea but my code got MLE for the 2000 node test case. Could you tell me why? Thanks!

    class Solution {
    public:
        int flag=0, ct=0;
        bool validTree(int n, vector<pair<int, int>>& edges) {
            vector<vector<int>> graph(n);
            vector<int> pre(n, -1), v(n, 0);
            for(int i=0;i<edges.size();i++)
            {
                graph[edges[i].first].push_back(edges[i].second);
                graph[edges[i].second].push_back(edges[i].first);
            }
            DFS(0, v, graph, -1);
            return flag==0&&ct==n;
        }
        
        void DFS(int r, vector<int>& visited, vector<vector<int>> graph, int pre) {
            if(flag==1) return;
            visited[r]=1;
            ct++;
            for(int i=0;i<graph[r].size();i++)
            {
                if(visited[graph[r][i]]==1&&graph[r][i]!=pre) 
                {
                    flag=1;
                    return;
                }
                if(graph[r][i]==pre) continue;
                //pre[graph[r][i]]=r;
                DFS(graph[r][i], visited, graph, r);
            }
        }
    };

Log in to reply
 

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