Graph Valid Tree medium

Problem Statement

Given n nodes labeled from 0 to n - 1 and a list of edges, where edges[i] = [u, v] represents a directed edge from node u to node v, determine if the edges form a valid tree.

A valid tree is a connected acyclic graph with n nodes and n-1 edges. A connected graph means that there is a path between any two nodes. An acyclic graph contains no cycles.

Example 1

Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]] Output: true Explanation: The given edges form a valid tree.

Example 2

Input: n = 5, edges = [[0,1],[1,2],[2,3],[3,4],[4,0]] Output: false Explanation: This graph has a cycle.

Steps

1. Validate Edge Count: Check if the number of edges is equal to n - 1. If not, it cannot be a valid tree.

2. Detect Cycles using Depth-First Search (DFS): We'll use DFS to traverse the graph and detect cycles. We'll maintain a visited array to track visited nodes and a recursionStack array to track nodes currently in the recursion stack (this helps us detect cycles). If we encounter a node already in recursionStack, it indicates a cycle.

3. Check Connectivity: After the DFS, we'll check if all nodes have been visited. If not, the graph is not connected.

Explanation

The core idea is to leverage Depth-First Search (DFS) to efficiently check for cycles and connectivity. A valid tree must satisfy two crucial properties:

• Acyclicity: No cycles should exist within the graph structure. DFS helps identify cycles by checking if we encounter a node that's already part of the current recursion path.
• Connectivity: There should be a path between any two nodes. We ensure this by checking if all nodes have been visited after the DFS traversal.

The recursionStack is key to detecting cycles. When exploring a node, it is marked in the recursionStack. When a node already present in recursionStack is encountered again, it means a cycle exists.

Code

#include <vector>

using namespace std;

class Solution {
public:
    bool validTree(int n, vector<vector<int>>& edges) {
        if (edges.size() != n - 1) return false; //Must have n-1 edges

        vector<vector<int>> adj(n);
        for (auto& edge : edges) {
            adj[edge[0]].push_back(edge[1]);
            adj[edge[1]].push_back(edge[0]); //Undirected graph
        }

        vector<bool> visited(n, false);
        vector<bool> recursionStack(n, false);

        function<bool(int)> dfs = [&](int u) {
            visited[u] = true;
            recursionStack[u] = true;

            for (int v : adj[u]) {
                if (!visited[v]) {
                    if (!dfs(v)) return false;
                } else if (recursionStack[v]) {
                    return false; //Cycle detected
                }
            }

            recursionStack[u] = false; //Remove from recursion stack after exploring
            return true;
        };

        if (!dfs(0)) return false; //Start DFS from node 0

        for (int i = 0; i < n; ++i) {
            if (!visited[i]) return false; //Check for connectivity
        }

        return true;
    }
};

Complexity

• Time Complexity: O(N + E), where N is the number of nodes and E is the number of edges. This is because DFS visits each node and edge once.
• Space Complexity: O(N) due to the visited, recursionStack, and adjacency list (adj). The recursion stack used by DFS also contributes to space complexity.