261. Graph Valid Tree

You have a graph of n nodes labeled from 0 to n - 1. You are given an integer n and a list of edges where edges[i] = [ai, bi] indicates that there is an undirected edge between nodes ai and bi in the graph.

Return true if the edges of the given graph make up a valid tree, and false otherwise.

• dfs solution
• Time : O(v + e)
• Space : O(v + e);

c++

class Solution {
    vector<int> v;
    bool dfs(vector<vector<int>>& g, int n, int from) {
        if(v[n]) return false;
        v[n] = 1;
        for(auto nxt : g[n]) {
            if(nxt == from) continue;
            if(!dfs(g,nxt,n)) return false;
        }
        return true;
    }
public:
    bool validTree(int n, vector<vector<int>>& edges) {
        vector<vector<int>> g(n);
        v = vector<int>(n,0);
        for(auto e : edges) {
            g[e[0]].push_back(e[1]);
            g[e[1]].push_back(e[0]);
        }
        return dfs(g,0,-1) and accumulate(v.begin(), v.end(), 0) == n;
    }
};

• union find solution
• Time : O(elogv + v)
• Space : O(v)

c++

class Solution {
    vector<int> g;
    int find(int n) {
        return g[n] == n ? n : g[n] = find(g[n]);
    }
public:
    bool validTree(int n, vector<vector<int>>& edges) {
        g = vector<int>(n,0);
        for(int i = 0; i < n; i++) g[i] = i;
        for(auto e : edges) {
            int n1 = find(e[0]), n2 = find(e[1]);
            if(n1 == n2) return false;
            g[n1] = g[n2] = min(n1, n2);
        }
        return !accumulate(g.begin(), g.end(), 0, [&](int s, int n) {return s + find(n);});
    }
};