</>EmbeddedInterview

Detect a cycle in a directed graph.

Medium"Coding: Systems, Bitmaps & Virtualization"
#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.