The problem. You're given an undirected graph with n vertices, numbered 0 to n - 1, and a list of edges. No edge is listed twice and no vertex is joined to itself. Return true if the graph contains a cycle — a route that leaves a vertex and comes back to it without using any edge twice.
n = 5, edges = [[0,1],[1,2],[2,3],[3,1],[3,4]] -> true (1 - 2 - 3 - 1)
n = 4, edges = [[0,1],[0,2],[1,3]] -> false (a tree)
n = 6, edges = [[0,1],[1,2],[3,4],[4,5],[5,3]] -> true (the loop is in the second piece)BFS and DFS answer what can I reach? Remember one extra fact per vertex and the same walk answers questions about the graph's shape. Remember where each vertex was reached from, and you can spot loops. Remember a colour, and you can split the vertices into two teams (next lesson). Either way it's still one walk: O(V + E).
Here's the key fact. In a graph with no cycle — a tree, or several trees — there is exactly one route between any two vertices. A cycle means some pair has two routes. During a DFS, a second route shows up as an edge to a vertex that's already visited.
One catch: in an undirected graph, the edge you just came along also leads to a visited vertex — your parent. That isn't a second route, it's the same edge seen from the other end. So each call remembers its parent and ignores it. Any other visited neighbour is a cycle.
An edge lies on a cycle exactly when its two ends are still connected without it. So remove each edge in turn and search from one end for the other.
function hasCycle(n, edges) { // An edge closes a cycle if its two ends are still connected without it. for (let skip = 0; skip < edges.length; skip++) { const adj = Array.from({ length: n }, () => []); edges.forEach(([u, v], i) => { if (i !== skip) { adj[u].push(v); adj[v].push(u); } }); const [from, to] = edges[skip]; const seen = new Array(n).fill(false); const stack = [from]; seen[from] = true; while (stack.length > 0) { const u = stack.pop(); if (u === to) return true; // reachable another way: this edge closes a cycle for (const v of adj[u]) { if (!seen[v]) { seen[v] = true; stack.push(v); } } } } return false;}Time O(E · (V + E)), space O(V + E). Each of the E edges rebuilds the graph and runs a whole search. It works, but it repeats almost the same search E times.
Walk each piece of the graph once. Every call dfs(u, parent) marks u visited and looks at its neighbours: skip the parent, return true for any other visited neighbour, and otherwise recurse. The outer loop starts a new walk from every vertex not yet visited, because the cycle might be in a piece the first walk never reaches.
Each call remembers where it came from; a visited neighbour that isn't the parent closes a loop. Try the tree too.
function hasCycle(n, edges) { const adj = Array.from({ length: n }, () => []); for (const [u, v] of edges) { adj[u].push(v); adj[v].push(u); } const visited = new Array(n).fill(false); const dfs = (u, parent) => { visited[u] = true; for (const v of adj[u]) { if (v === parent) continue; // the edge we just came along: not a cycle if (visited[v]) return true; // reached again by another route: a cycle if (dfs(v, u)) return true; } return false; }; for (let s = 0; s < n; s++) { if (!visited[s] && dfs(s, -1)) return true; // check every piece of the graph } return false;}Time O(V + E), space O(V + E). Every vertex is visited once and every edge is looked at from both ends. The adjacency list takes O(V + E); the recursion can be V calls deep.
A shortcut worth knowing: a graph with no cycle has at most V - 1 edges. So if edges.length >= n, the answer is true before you even search.
u - v - u is then a real loop, but skipping the parent vertex hides it. If duplicates can appear, skip the parent edge (by its index) instead.n - 1 edges and that one walk reaches every vertex.