Cycle Detection using Union-Find C++: Story

🕯️ The War of the Loop — Cycle Detection with Union-Find and Rank

“Alliances are not just built on trust…
but on the weight of kingdoms.
For when two kings meet,
the mightier must wear the crown.”
— Scrolls of Ancient Balance, Volume V

---

🌌 Prologue: The Shattered Thrones

In the age before maps, before borders, and long before crowns were melted into peace, the world was ruled by scattered tribes. Each man and woman declared their bloodline royal, each kingdom a lonely fortress with no bridges to another.

But then came an age of roads — alliances, treaties, marriages between houses.
And with it, came the fear of something ancient:
The Cycle — a cursed symbol of kingdoms forming bonds with themselves, unaware.

The Monks of Memory, the Union-Finders, were summoned.
Their vow?

“Unite the world if it can be…
but the moment you see a loop, speak — and halt the madness.”

---

🏰 The Scroll of Might — A Class Born of Rank

#include <iostream>
#include <vector>
using namespace std;

Thus, the scribes prepared the tools of tracking:

The Scroll of Bloodlines — to remember each ruler
The Ledger of Might — to record the strength of their houses

class UnionFind {
    vector<int> parent;
    vector<int> rank;

public:
    UnionFind(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        for (int i = 0; i < n; ++i)
            parent[i] = i;
    }

Each soul was given a name — parent[i] = i — claiming their own banner.

Each house had no soldiers yet, but pride enough — rank[i] = 0.

---

🧭 The Pilgrimage to the True King

    int find(int v) {
        if (parent[v] == v)
            return v;
        return parent[v] = find(parent[v]);
    }

When a warrior sought to know whom he truly served, he walked the path of banners — tracing the lineage of parents. And when he reached the true king, he returned — not silently — but rewriting the scrolls to make the path shorter for all who’d follow.

This was not just travel.
This was path compression.
This was the truth made fast.

---

👑 The Crown Goes to the Mightier

    bool unionSets(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b)
            return false;

        if (rank[a] < rank[b])
            parent[a] = b;
        else if (rank[a] > rank[b])
            parent[b] = a;
        else {
            parent[b] = a;
            rank[a]++;
        }

        return true;
    }

Then came the mighty ritual of merging kingdoms.
The two kings — a and b — would be summoned before the monks.

First, their true thrones were sought: find(a), find(b).

If the thrones were the same, the monks would freeze.

“These kings already rule the same land…
A cycle is forming.”

But if the thrones were different, the ritual proceeded:

• If one kingdom was weaker (rank[a] < rank[b]), it bowed to the stronger.
• If stronger, it absorbed the other.
• If equal, one was chosen — and its might (rank) grew.

“Let no weak house dominate a strong one,” the monks chanted.
“Let might flow upward, so that chaos does not.”

---

⚔️ The Great Alliance

bool containsCycle(int n, vector<pair<int, int>> &edges) {
    UnionFind uf(n);
    for (auto &[u, v] : edges) {
        if (!uf.unionSets(u, v))
            return true;
    }
    return false;
}

When the kingdoms came to unite — road by road, bond by bond — each edge in edges was a treaty.

But each time a bond was proposed — between u and v —
The monks asked:

“Do you already serve the same king?”

If yes — a cycle.

“You are looping! Halt this folly.”

Return true.

If no — the kingdoms merged properly.

When all bonds were passed safely, and no whispers of betrayal stirred in the wind —

Return false.

---

🧪 The Test of Fire

int main() {
    int n = 6;
    vector<pair<int, int>> edges = {
        {0, 1}, {1, 2}, {2, 3}, {3, 4}, {4, 1}
    };

    if (containsCycle(n, edges))
        cout << "Cycle detected\n";
    else
        cout << "No cycle\n";
}

One dusk, the kingdoms gathered with ambition.
They drew maps. Proposed roads.

• 0-1? Safe.
• 1-2? A wise pact.
• 2-3? Let the banners fly.
• 3-4? Let peace reign.
• 4-1?

The monks raised their hands.

“You march back to your own gate.”
“You form a cycle.”
“This road must not be walked.”

“Cycle detected.”

---

🧠 And Now, Etch This in Your Soul

• find(v) — The pilgrim’s path to his true king, made shorter with every journey.
• unionSets(a, b) — The rite of unification. The strong absorbs the weak. The equal gains rank.
• If a warrior tries to merge with what he already serves — A cycle is found.

This tale of kings and banners may wear the robe of fiction —
But when you sit in an interview, and they say “detect cycles,”
Let this legend rise like thunder.

Let the code be your sword.
Let the story be your memory.
And let no cycle go unnoticed in your kingdom of logic.