Cycle Detection in Undirected Graph

DFS approach

boolean hasCycle(int u, int parent, List[] graph, boolean[] visited) {
  visited[u] = true;
  for (int v : graph[u]) {
    if (!visited[v]) { if (hasCycle(v, u, graph, visited)) return true; }
    else if (v != parent) return true;
  }
  return false;
}

Union-Find approach

For each edge (u,v): find(u) == find(v) → cycle. Else union. O((V+E)·α(V)).

Complexity

DFS: O(V+E). Union-Find: O((V+E)·α(V)) — marginally slower but works for streaming edge inputs.

Multi-component handling

Iterate over all vertices, launching DFS from unvisited ones.