Summary of "G-12. Detect a Cycle in an Undirected Graph using DFS | C++ | Java"

Detecting a cycle in an undirected graph using DFS

Use depth-first search (DFS) to determine whether any simple cycle exists in an undirected graph.
During DFS, pass the parent node so that encountering the parent as a visited neighbor is not treated as a cycle.
If you encounter an adjacent node that is already visited and is not the parent, a cycle exists.
For graphs with multiple connected components, run DFS from every unvisited node.

Data structures
- visited[]: boolean array initialized to false for all nodes.
- adjacency list representation of the graph.
- DFS function signature: dfs(node, parent)
DFS function (returns boolean: true if a cycle is found in this call/subtree)
- visited[node] = true
- For each neighbor v in adjacency[node]:
  - If visited[v] == false:
    - If dfs(v, node) returns true, immediately return true
  - Else (visited[v] == true):
    - If v != parent, then return true (visited non-parent neighbor ⇒ cycle)
- After exploring all neighbors, return false (no cycle found from this node)
Main driver (handles multiple components)
- For every node i in 1..N (or 0..N-1 for 0-based indexing):
  - If visited[i] == false:
    - If dfs(i, -1) returns true, then there exists a cycle (stop and report)
- If none of the DFS calls returned true, report no cycle

Key check: if a visited neighbor is not the parent, that indicates a cycle.

Start DFS at node 1: mark visited, explore neighbors (2 then 3).
Example chain explored: 1 → 2 → 5 → 7 → 6 → 3 → 4.
If DFS reaches a node whose neighbor is already visited and is not its parent (for example encountering node 1 from a node that is not its parent), that is detected as a cycle.
When any DFS call returns true, propagate that true back up the recursion stack to the driver and conclude the graph has a cycle.

Always pass a parent argument in DFS to ignore the immediate back-edge to the parent.
Initialize visited[] to false before starting; use -1 (or null) as the parent for initial calls.
For graphs with multiple components, iterate over all nodes and call DFS for unvisited nodes.
Use an adjacency list representation for the graph input.

Time: O(V + E) — every vertex and every edge is processed a constant number of times during DFS.
Space: O(V) for visited[] plus recursion stack, which is O(V) in the worst case (so overall O(V) auxiliary space).

Example implementations are commonly shown in C++ and Java.
Dry-run the algorithm on multiple graphs to reinforce understanding and recursion concepts.

Presenter / channel host (unnamed in subtitles).
The video references its own prior videos and lecture series and shows code in C++ and Java.
Background music is played at the end of the video.