Graph Valid Tree C++ solution using DFS


  • 0
    A
    class Solution {
        int cc;
    public:
        bool dfs(int src, int target, vector<unordered_set<int>> &adj, vector<bool> &marked) {
            // dfs  to check for connectedness from src to target
            for (auto &dest : adj[src]) {
                if (dest == target) return true;
                if (!marked[dest]) {
                    marked[dest] = true;
                    if(dfs(dest, target, adj, marked)) return true;
                }
            }
            return false;
        }
         void dfs(int src, vector<unordered_set<int>> &adj, vector<bool> &marked) {
            // plain dfs from src
            for (auto &dest : adj[src]) {
                if (!marked[dest]) {
                    marked[dest] = true;
                    dfs(dest, adj, marked);
                }
            }
            
        }
        bool graph_connected(vector<unordered_set<int>> &adj, int n) {
            // count number of components
            cc = 0;
            vector<bool> marked(n, false);
            for (size_t src = 0; src < n; ++src) {
                if(!marked[src]) {
                    marked[src] = true;
                    dfs(src, adj, marked);
                    cc++;
                    if (cc > 1) return false; // more than one connected component
                }
            }
            return true;
        }
        bool validTree(int n, vector<pair<int, int>>& edges) {
            if(n <= 1) return true;
            vector<unordered_set<int>> adj(n);
            for (auto &e : edges) {
                    vector<bool> marked(n, false);
                    marked[e.first] = true;
                    if (dfs(e.first, e.second, adj, marked)) return false; // cycle exists
                    adj[e.first].insert(e.second);
                    adj[e.second].insert(e.first);
            }
           
            return graph_connected(adj, n); // check if only one component exists
            
        }
    };

Log in to reply
 

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