Graph Valid Tree

Problem

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

Examples

Example 1:

Input:
n = 5
edges = [[0, 1], [0, 2], [0, 3], [1, 4]]

Output:
true

You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges

Example 2:

Input:
n = 5
edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]

Output:
false

Constraints

• 1 <= n <= 100
• 0 <= edges.length <= n * (n - 1) / 2

You should aim for a solution as good or better than O(V + E) time and O(V + E) space, where V is the number vertices and E is the number of edges in the graph.

Solution

A tree over n nodes must have n-1 edges, and it must be possible to perform a BFS without encountering a cycle. Need to be careful about trivial self-loops and trivial cycles back and forth.

class Solution {
    struct Node {
        int parent;
        int n;
    };
 
public:
    bool validTree(int n, vector<vector<int>>& edges) {
        // Base case, edges do not match
        if (edges.size() != n - 1) {
            return false;
        }
        std::vector<std::unordered_set<int>> adj(n);
 
        // Make graph
        for (const auto &e : edges) {
            adj[e[0]].insert(e[1]);
            adj[e[1]].insert(e[0]);
        }
 
        std::queue<Node> open;
        std::unordered_set<int> closed;
        open.emplace(-1, 0);
        closed.insert(0);
 
        while (!open.empty()) {
            auto [par, node] = open.front();
            open.pop();
            for (const auto &n : adj[node]) {
                // Prevent trivial and self cycles
                if (n == par || n == node) {
                    continue;
                }
                // Non-trivial cycle
                if (closed.contains(n)) {
                    return false;
                }
                closed.insert(n);
                open.emplace(node, n);
            }
        }
        return closed.size() == n;
    }
};