DFS Cycle and Connectivity Check
Intuition
A valid tree with n nodes must have exactly n - 1 edges, be fully connected, and contain no cycles. We first check the edge count: if it is not n - 1, we immediately return false. Then we build an adjacency list and run DFS from node 0, tracking visited nodes. If any unvisited neighbor leads back to a visited node that is not the parent, a cycle exists. After DFS completes, we verify all nodes were visited (connectivity check). The parent tracking is essential for undirected graphs to avoid falsely detecting the edge we just traversed as a cycle.
Algorithm
- If the number of edges is not `n - 1`, return false immediately.
- Build an adjacency list from the edges.
- Run DFS from node 0, keeping track of visited nodes and each node's parent.
- For each neighbor of the current node, skip the parent. If a neighbor is already visited, a cycle exists -- return false. Otherwise, recurse.
- After DFS, check if all `n` nodes were visited. If not, the graph is disconnected.
- Return true only if no cycle was found and all nodes were visited.
Time
O(V + E) where V is the number of nodes and E is the number of edgesSpaceO(V + E) for the adjacency list and visited setCode (C++ · Java · Python · Go)
class Solution {
public:
bool validTree(int n, vector<vector<int>>& edges) {
if (edges.size() != n - 1) return false;
vector<vector<int>> graph(n);
for (auto& e : edges) {
graph[e[0]].push_back(e[1]);
graph[e[1]].push_back(e[0]);
}
vector<bool> visited(n, false);
if (hasCycle(graph, visited, 0, -1)) return false;
for (bool v : visited) {
if (!v) return false;
}
return true;
}
private:
bool hasCycle(vector<vector<int>>& graph, vector<bool>& visited, int node, int parent) {
visited[node] = true;
for (int neighbor : graph[node]) {
if (neighbor == parent) continue;
if (visited[neighbor]) return true;
if (hasCycle(graph, visited, neighbor, node)) return true;
}
return false;
}
};class Solution {
public boolean validTree(int n, int[][] edges) {
if (edges.length != n - 1) return false;
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
for (int[] e : edges) {
graph.get(e[0]).add(e[1]);
graph.get(e[1]).add(e[0]);
}
boolean[] visited = new boolean[n];
if (hasCycle(graph, visited, 0, -1)) return false;
for (boolean v : visited) {
if (!v) return false;
}
return true;
}
private boolean hasCycle(List<List<Integer>> graph, boolean[] visited, int node, int parent) {
visited[node] = true;
for (int neighbor : graph.get(node)) {
if (neighbor == parent) continue;
if (visited[neighbor]) return true;
if (hasCycle(graph, visited, neighbor, node)) return true;
}
return false;
}
}from typing import List
class Solution:
def validTree(self, n: int, edges: List[List[int]]) -> bool:
if len(edges) != n - 1:
return False
graph = [[] for _ in range(n)]
for a, b in edges:
graph[a].append(b)
graph[b].append(a)
visited = set()
def has_cycle(node, parent):
visited.add(node)
for neighbor in graph[node]:
if neighbor == parent:
continue
if neighbor in visited:
return True
if has_cycle(neighbor, node):
return True
return False
if has_cycle(0, -1):
return False
return len(visited) == nfunc validTree(n int, edges [][]int) bool {
if len(edges) != n-1 {
return false
}
graph := make([][]int, n)
for i := range graph {
graph[i] = []int{}
}
for _, e := range edges {
graph[e[0]] = append(graph[e[0]], e[1])
graph[e[1]] = append(graph[e[1]], e[0])
}
visited := make([]bool, n)
var hasCycle func(node, parent int) bool
hasCycle = func(node, parent int) bool {
visited[node] = true
for _, neighbor := range graph[node] {
if neighbor == parent {
continue
}
if visited[neighbor] {
return true
}
if hasCycle(neighbor, node) {
return true
}
}
return false
}
if hasCycle(0, -1) {
return false
}
for _, v := range visited {
if !v {
return false
}
}
return true
}