DEV Community

Harsh Mishra
Harsh Mishra

Posted on

Cycle Detection for Directed Graphs(DFS with recursion stack) C++: Story

#algorithms #programming #cpp

🕳️ The Spiral Citadel — Cycle Detection in Directed Graphs using DFS with Recursion Stack

“Some staircases do not descend — they spiral. And in such towers, where a room leads back to itself, a curse brews in silence.”
— The Tome of Tethered Realms, Chapter XIII

🏛️ Prologue: The Spiral Citadel

In a land where kingdoms connected not by roads but by commands, rose a mysterious citadel — The Spiral Citadel.

Each room was ruled by a lord, and each lord had power only to summon others forward — never backward. These were directed corridors, each a one-way decree.

But rumors began to rise from the spiral halls.
That a lord could, by chain of command, be summoned back to himself.

“A loop,” the scholars feared.
“A cursed command chain.
A cycle.”

The Council of Graphwalkers dispatched a lone Seeker — trained in the art of recursion, memory, and truth-finding.

Their weapon: Depth-First Sight.
Their shield: The Recursion Stack.

🧭 The Tools of the Seeker 

#include <iostream>
#include <vector>
using namespace std;
Enter fullscreen mode Exit fullscreen mode

Scrolls, ink, and the memory of corridors are gathered.

class Graph {
    int V;
    vector<vector<int>> adj;

public:
    Graph(int V) {
        this->V = V;
        adj.resize(V);
    }

    void addEdge(int u, int v) {
        adj[u].push_back(v); // One-way passage from u to v
    }
Enter fullscreen mode Exit fullscreen mode

Each addEdge(u, v) is not a path, but a summon.
Lord u orders Lord v — a command chain.

There is no return unless someone somewhere down the chain returns to u.

đź‘Ł The Ritual of Descent 

    bool dfs(int node, vector<bool>& visited, vector<bool>& inRecStack) {
        visited[node] = true;
        inRecStack[node] = true;
Enter fullscreen mode Exit fullscreen mode

The Seeker steps into a room, and places a mark: "I have visited."

But deeper still, they place another sigil:
"I am currently here — this node lies in my path of descent."

This is inRecStack[node] = true.

        for (int neighbor : adj[node]) {
            if (!visited[neighbor]) {
                if (dfs(neighbor, visited, inRecStack))
                    return true;
Enter fullscreen mode Exit fullscreen mode

Each room contains scrolls of commands: "Visit Lord X next."

If Lord X hasn’t been explored yet, the Seeker walks onward — descending further into the Citadel’s spiraling halls.

The descent continues. The recursion deepens.

            } else if (inRecStack[neighbor]) {
                return true;
            }
Enter fullscreen mode Exit fullscreen mode

But suddenly — a cold chill.
A scroll declares:

“Summon Lord X.”

And the Seeker realizes…

“I have already passed through X.
And I never exited that path.”

X is still in my recursion path.

I’ve returned to a room mid-descent.

This is not just a revisit — it is a spiral.
A cycle.

return true;

🧹 The Ascent & Cleansing 

        }

        inRecStack[node] = false;
        return false;
    }
Enter fullscreen mode Exit fullscreen mode

Having fully explored all neighbors without spiraling, the Seeker erases the sigil:
"I am no longer here."

He steps back — recursion unwinds.
One room at a time. The spiral was avoided.

🛡️ The Grand March Across Realms 

    bool containsCycle() {
        vector<bool> visited(V, false);
        vector<bool> inRecStack(V, false);

        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                if (dfs(i, visited, inRecStack))
                    return true;
            }
        }

        return false;
    }
};
Enter fullscreen mode Exit fullscreen mode

The Seeker knows some Citadels are vast — with multiple towers disconnected.
So they begin at every unvisited chamber. A fresh quest each time.

If any search uncovers a spiral, a cursed cycle — the prophecy is true:

"The Spiral Citadel harbors the forbidden."
return true;

Otherwise, the halls are clear. The curse is a myth — for now.

🧪 The Chronicle of a Curse 

int main() {
    Graph g(6);
    g.addEdge(0, 1);
    g.addEdge(1, 2);
    g.addEdge(2, 3);
    g.addEdge(3, 4);
    g.addEdge(4, 2); // <-- cursed spiral
    g.addEdge(5, 0);

    if (g.containsCycle())
        cout << "Cycle detected\n";
    else
        cout << "No cycle\n";
}
Enter fullscreen mode Exit fullscreen mode

The Seeker enters the Citadel at room 0.
Command chains lead deeper: 0 → 1 → 2 → 3 → 4 → 2.

A gasp.
Room 2? Again? And I never exited?

A spiral.
A curse.
A cycle.

"Cycle detected"

🔥 Carve This Into Memory:

  • visited[] tells you “Have I ever been here?”
  • inRecStack[] whispers “Am I currently here?”
  • A revisit to a node still on the current path signals a cycle.
  • DFS with recursion tracks the present trail — not just footprints.
  • If you touch your own path before you’ve returned, you’re not walking — you’re spinning.

In the interviews, when asked:

“How would you detect cycles in a directed graph?”

Summon the Spiral Citadel in your mind.
Let the recursion stack guide your steps.
And listen for your own footsteps… coming from ahead.

Top comments (0)