DFS Recursive C++


  • 0
    X
    class Solution {
    public:
        bool validTree(int n, vector<pair<int, int>>& edges) {
            vector<vector<int>> neighbors (n, vector<int> ());
            vector<bool> nodesVisited (n, false);
            int edgesSize = edges.size() + 1;
            
            int first, second;
            for(int i = 0; i < edges.size(); i++){
                first = edges[i].first;
                second = edges[i].second;
                neighbors[second].push_back(first);
                neighbors[first].push_back(second);
            }
            
            dfs(edges, nodesVisited, edgesSize, neighbors, 0);
            for(int i = 0; i < n; i++)
                if(!nodesVisited[i]) return false;
            if(edgesSize > 0) return false;
            return true;
        }
        void dfs(vector<pair<int, int>>& edges, vector<bool> &nodesVisited, int &edgesSize, vector<vector<int>> &neighbors, int node){
            if(nodesVisited[node]) return;
            else{
                nodesVisited[node] = true;
                edgesSize--;
            }
            for(int i = 0; i < neighbors[node].size(); i++){
                if(neighbors[node][i] != node)
                    dfs(edges, nodesVisited, edgesSize, neighbors, neighbors[node][i]);
            }
            return;
        }
    };

Log in to reply
 

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