Detect a cycle in a directed graph.
#include <stdbool.h>
#define MAXN 16
static int adj[MAXN][MAXN], deg[MAXN]; /* adjacency lists */
static int color[MAXN]; /* 0 = white (unvisited), 1 = grey (on stack), 2 = black (done) */
static bool dfs_cycle(int u)
{
color[u] = 1;
for (int k = 0; k < deg[u]; k++) {
int v = adj[u][k];
if (color[v] == 1) return true; /* back edge to a node on the current path */
if (color[v] == 0 && dfs_cycle(v)) return true;
}
color[u] = 2;
return false;
}
bool has_cycle(int n)
{
for (int i = 0; i < n; i++) color[i] = 0;
for (int i = 0; i < n; i++)
if (color[i] == 0 && dfs_cycle(i)) return true;
return false;
}
Points: three-colour DFS: reaching a grey node (still on the recursion stack) means a back edge, i.e. a cycle; black nodes are finished and safe. O(V + E). For undirected graphs, track the parent instead. Embedded and systems uses: lock-order validation (Linux lockdep builds a graph of lock dependencies and reports cycles = potential deadlocks), detecting circular dependencies between drivers or build targets. Recursion depth equals the path length, so use an explicit stack on small MCUs.