# Cycle Detection in [[graph|Graph]]
Variant: [[course-schedule]]. Equivalent to validate a graph is a tree.
- Approaches
- [[topological-sort]] (in directed graph)
- [[dfs|DFS]] or [[bfs|BFS]]
- [[union-find]]
## DFS Approach
```python
if len(edges) != n - 1:
return False
adj = [[] for _ in range(n)]
for v, w in edges:
adj[v].append(w)
adj[w].append(v)
visited = [False] * n
counter = 0
def dfs(v, p) -> bool: # prevent backtracking to parent
# returns True if v is a valid subtree
nonlocal adj, visited, counter
if visited[v]:
return False
visited[v] = True
counter += 1
return all(dfs(w, v) for w in adj[v] if w != p)
res = dfs(0, -1)
return res and counter == n
```
## BFS Approach
```python
if len(edges) != n - 1:
return False
adj = [[] for _ in range(n)]
for v, w in edges:
adj[v].append(w)
adj[w].append(v)
parent = {0: -1}
queue = deque([0])
while queue:
v = queue.popleft()
p = parent[v]
for w in adj[v]:
if w == p:
continue
if w in parent:
return False
parent[w] = v
queue.append(w)
return len(parent) == n
```