DEV Community

Harsh Mishra
Harsh Mishra

Posted on

Cycle Detection for Undirected Graphs(DFS with parent tracking) C++: Story

#algorithms #cpp #programming

🕯️ The Web of Echoes — Cycle Detection in Undirected Graph using DFS with Parent Tracking

"In a forest of whispers, when a voice returns not from where it came...
beware the echo — for it carries the shape of a loop."
— The Shadowman’s Codex, Page 42

🌲 Prologue: The Whispering Woods

Long ago, nestled in the heart of the realm, stood a vast, mysterious forest. This was no ordinary wood — it was said that the paths twisted like tales, the branches bent like lies, and voices sometimes returned from directions they never went.

The kingdom called it: Graph.

The nodes were villages. The edges — footpaths.
Unseen from above, this forest held secrets:
Cycles — paths that led back to themselves without warning.

And so the Rangers of the Order of Depth were summoned — their mission clear:

“Traverse the forest.
If you hear your voice echo back —
but not from the direction it came —
speak of the Cycle, and light the beacon.”

🗺️ The Scroll of Secrets 

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

The order brought parchment and ink. They mapped the land.

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);
        adj[v].push_back(u); // Because the paths go both ways
    }
Enter fullscreen mode Exit fullscreen mode

Each edge is a trail between two villages — bidirectional and blind.
One can go from u to v, or from v to u, without a signpost.

But in this symmetry lies danger: you may return to where you started, believing it’s a new place.

🧭 The Ranger’s Journey 

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

A ranger steps into the unknown — the village of node.
He marks it: "I have been here."
This is done with visited[node] = true.

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

He sees a path — a neighboring village.
If it's untouched, he walks — and records where he came from: parent.

“If my voice returns… it must come from where I’ve been.”

He proceeds deeper.

            } else if (neighbor != parent) {
                return true;
            }
    }
    // No cycle found in this branch
    return false;
Enter fullscreen mode Exit fullscreen mode

But wait — a voice calls from a place he already marked.
And it didn’t come from the direction he just came…

He knows, instantly:

“This is no echo…
This is a loop.”

A cycle.
He turns back, alarmed. return true;

🔥 The Call of the Beacons 

    bool containsCycle() {
        vector<bool> visited(V, false);
        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                if (dfs(i, -1, visited))
                    return true;
            }
        }
        return false;
    }
};
Enter fullscreen mode Exit fullscreen mode

Each ranger begins at an unexplored village.
If there’s more than one forest, more than one starting point, the order ensures all are watched.

“For even if the east is quiet,
the west may whisper trouble.”

If any call returns with a Cycle, the whole order signals the capital:

return true.

If not — the realm sleeps safely tonight.

🧪 The Chronicle of a Run 

int main() {
    Graph g(5);
    g.addEdge(0, 1);
    g.addEdge(1, 2);
    g.addEdge(2, 3);
    g.addEdge(3, 4);
    g.addEdge(4, 1);

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

The rangers are dispatched.

  • 0 → 1 → 2 → 3 → 4
  • But 4 hears a voice from 1… not the path it just came from.

“A second entry into a circle,” one ranger says.
“This is no mistake.
Cycle detected.”

đź’ˇ Remember This When the Fire is Lit

  • The visited[] array marks your footprints.
  • The parent ensures you don’t mistake your own steps for a cycle.
  • A back edge to any visited node that isn't your parent is a cycle.
  • DFS walks into the unknown — and listens carefully for the wrong echo.

In the eyes of kings and interviewers alike,
this tale is not just a narrative —
it’s your intuition wrapped in memory.

When they say:

“Can you detect cycles in an undirected graph?”

Let the forest unfold in your mind.
Let the whispers return.
And let your code walk like a ranger through the trees.

Top comments (0)