# [261\. Graph Valid Tree](https://leetcode.com/problems/graph-valid-tree/)

:::spoiler Solution

class Solution {
public:
    bool validTree(int n, vector<vector<int>>& edges)
    {
        vector<vector<int>> graph(n, vector<int>());
        for (auto& edge : edges)
        {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }

        unordered_set<int> seen;
        return dfs(graph, seen, 0, -1) && seen.size() == n;        
    }

    bool dfs(vector<vector<int>>& graph, unordered_set<int>& seen, int node, int parent)
    {
        if (seen.count(node)) return false;

        seen.insert(node);
        
        for(int nei : graph[node])
        {
            if (parent != nei)
            {
                if (!dfs(graph, seen, nei, node))
                    return false;
            }
        }
        return true;
    }    
};

- 時間複雜度：$O(V + E)$
- 空間複雜度：$O(V + E)$
:::