In an undirected graph every edge is a two-way street, so you'll always "see" the node you came from. The trick: ignore your parent. Any other already-visited neighbor means a cycle.
DFS from any node, remembering who you came from (parent). When you reach a neighbor that's already visited and isn't your parent, you've found a second way into that node, that's a cycle.
u–v is stored both waysv you'll always see u againbool dfs(int u, int parent, vector<vector<int>>& adj, vector<bool>& vis) {
vis[u] = true;
for (int v : adj[u]) {
if (!vis[v]) {
if (dfs(v, u, adj, vis)) return true;
} else if (v != parent) {
return true; // visited & not parent → cycle
}
}
return false;
}
bool hasCycle(int n, vector<vector<int>>& adj) {
vector<bool> vis(n, false);
for (int i = 0; i < n; i++)
if (!vis[i] && dfs(i, -1, adj, vis))
return true; // check every component
return false;
}Standard DFS, each vertex and edge touched once.
Visited array plus recursion stack depth.
A visited neighbor that isn't the parent = the second path into a node.
V nodes is a tree iff it has exactly V-1 edges and no cycle.