Cycle Detection in Graphs: Undirected & Directed

A cycle is a path that returns to where it started. Detecting cycles tells you whether a dependency graph is resolvable, whether a graph is a tree, or whether a schedule is feasible. The technique differs by graph type: undirected graphs use union-find or DFS with a parent check, while directed graphs use a three-color DFS that distinguishes “still on the stack” from “fully done.”

Undirected graphs with union-find

In an undirected graph, process each edge (u, v). If u and v are already in the same set, adding this edge closes a loop — a cycle. Otherwise union them. This is union-find (disjoint set union), the same structure behind Kruskal’s MST.

struct DSU {
    std::vector<int> parent, rank_;
    DSU(int n): parent(n), rank_(n, 0) { for (int i=0;i<n;i++) parent[i]=i; }
    int find(int x){ return parent[x]==x ? x : parent[x]=find(parent[x]); }
    bool unite(int a,int b){
        a=find(a); b=find(b);
        if(a==b) return false;            // already connected -> cycle
        if(rank_[a]<rank_[b]) std::swap(a,b);
        parent[b]=a;
        if(rank_[a]==rank_[b]) rank_[a]++;
        return true;
    }
};
bool hasCycleUndirected(int V, const std::vector<std::pair<int,int>>& edges){
    DSU dsu(V);
    for (auto [u,v] : edges) if(!dsu.unite(u,v)) return true;
    return false;
}

class DSU {
    int[] parent, rank_;
    DSU(int n){ parent=new int[n]; rank_=new int[n];
        for(int i=0;i<n;i++) parent[i]=i; }
    int find(int x){ return parent[x]==x ? x : (parent[x]=find(parent[x])); }
    boolean unite(int a,int b){
        a=find(a); b=find(b);
        if(a==b) return false;            // already connected -> cycle
        if(rank_[a]<rank_[b]){ int t=a; a=b; b=t; }
        parent[b]=a;
        if(rank_[a]==rank_[b]) rank_[a]++;
        return true;
    }
}
boolean hasCycleUndirected(int V, int[][] edges){
    DSU dsu = new DSU(V);
    for(int[] e: edges) if(!dsu.unite(e[0], e[1])) return true;
    return false;
}

function hasCycleUndirected(V, edges) {
  const parent = Array.from({ length: V }, (_, i) => i);
  const rank = new Array(V).fill(0);
  function find(x) { return parent[x] === x ? x : (parent[x] = find(parent[x])); }
  function unite(a, b) {
    a = find(a); b = find(b);
    if (a === b) return false;            // already connected -> cycle
    if (rank[a] < rank[b]) [a, b] = [b, a];
    parent[b] = a;
    if (rank[a] === rank[b]) rank[a]++;
    return true;
  }
  for (const [u, v] of edges) if (!unite(u, v)) return true;
  return false;
}

def has_cycle_undirected(V, edges):
    parent = list(range(V))
    rank = [0] * V
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    def unite(a, b):
        a, b = find(a), find(b)
        if a == b:
            return False                  # already connected -> cycle
        if rank[a] < rank[b]:
            a, b = b, a
        parent[b] = a
        if rank[a] == rank[b]:
            rank[a] += 1
        return True
    for u, v in edges:
        if not unite(u, v):
            return True
    return False

For beginners: An undirected DFS alternative also works — run DFS, and if you reach an already-visited neighbor that is not the vertex you came from (the parent), you’ve found a cycle.

Directed graphs with three colors

In a directed graph, returning to a visited vertex is not automatically a cycle — it might just be a second path to a finished vertex. The fix is three colors:

White (0): unvisited.
Gray (1): on the current DFS path (in the recursion stack).
Black (2): fully explored, all descendants done.

A gray vertex reached again means a back edge — a true cycle.

bool dfsDir(int u, const std::vector<std::vector<int>>& adj, std::vector<int>& color){
    color[u] = 1;                          // gray: on current path
    for (int v : adj[u]) {
        if (color[v] == 1) return true;    // back edge -> cycle
        if (color[v] == 0 && dfsDir(v, adj, color)) return true;
    }
    color[u] = 2;                          // black: done
    return false;
}
bool hasCycleDirected(const std::vector<std::vector<int>>& adj){
    std::vector<int> color(adj.size(), 0);
    for (int i = 0; i < (int)adj.size(); i++)
        if (color[i] == 0 && dfsDir(i, adj, color)) return true;
    return false;
}

boolean dfsDir(int u, List<List<Integer>> adj, int[] color){
    color[u] = 1;                          // gray: on current path
    for (int v : adj.get(u)) {
        if (color[v] == 1) return true;    // back edge -> cycle
        if (color[v] == 0 && dfsDir(v, adj, color)) return true;
    }
    color[u] = 2;                          // black: done
    return false;
}
boolean hasCycleDirected(List<List<Integer>> adj){
    int[] color = new int[adj.size()];
    for (int i = 0; i < adj.size(); i++)
        if (color[i] == 0 && dfsDir(i, adj, color)) return true;
    return false;
}

function hasCycleDirected(adj) {
  const color = new Array(adj.length).fill(0);
  function dfs(u) {
    color[u] = 1;                          // gray: on current path
    for (const v of adj[u]) {
      if (color[v] === 1) return true;     // back edge -> cycle
      if (color[v] === 0 && dfs(v)) return true;
    }
    color[u] = 2;                          // black: done
    return false;
  }
  for (let i = 0; i < adj.length; i++)
    if (color[i] === 0 && dfs(i)) return true;
  return false;
}

def has_cycle_directed(adj):
    color = [0] * len(adj)
    def dfs(u):
        color[u] = 1                       # gray: on current path
        for v in adj[u]:
            if color[v] == 1:              # back edge -> cycle
                return True
            if color[v] == 0 and dfs(v):
                return True
        color[u] = 2                       # black: done
        return False
    return any(color[i] == 0 and dfs(i) for i in range(len(adj)))

Pitfall: Using a single boolean visited array for a directed graph gives false positives — a vertex reachable by two separate paths looks like a cycle. You need the gray/black distinction (or an explicit “in current recursion stack” set).

Complexity

Both approaches run in O(V + E) time. Union-find uses O(V) space; the color DFS uses O(V) for the color array plus recursion stack. The near-O(1) amortized union-find operations come from path compression and union by rank.

A directed graph that has no cycle is a DAG, which you can linearize with topological sort — coming up next.