SCC, bridge আর articulation point

১ · একমুখী রাস্তার শহর — গিয়ে কি ফিরে আসা যায়?

পুরান ঢাকার অনেক গলি একমুখী। রিকশা নিয়ে আপনি এক মোড় থেকে আরেক মোড়ে সহজেই চলে গেলেন, কিন্তু ফেরার সময় দেখলেন সেই গলিতে উল্টো দিকে ঢোকা নিষেধ। তখন প্রশ্ন: অন্য গলি ঘুরে ফেরা কি আদৌ সম্ভব? ট্রাফিক বিভাগের কাছে প্রশ্নটি আরও বড়: শহরের কোন কোন মোড়ের দল এমন, যাদের ভেতরে যেকোনো মোড় থেকে যেকোনো মোড়ে যাওয়া আর ফিরে আসা যায়?

গ্রাফের ভাষায় মোড়গুলো vertex, একমুখী রাস্তাগুলো দিকসহ edge — এমন গ্রাফকে বলে directed graph. u থেকে edge ধরে ধরে v-তে পৌঁছানো গেলে বলি v, u থেকে reachable. Undirected গ্রাফে (পর্ব ৩৯) এই সম্পর্ক দুদিকেই একসাথে সত্য, কিন্তু directed গ্রাফে নয়: u থেকে v-তে যাওয়া গেলেও v থেকে u-তে ফেরার পথ না-ও থাকতে পারে।

“↔” সম্পর্কটি একটি equivalence relation: প্রত্যেকে নিজের সাথে পরস্পর reachable (শূন্য দৈর্ঘ্যের পথ), সম্পর্কটি প্রতিসম, আর u ↔ v ও v ↔ w হলে দুটি পথ জুড়ে u ↔ w. তাই পর্ব ৩৩-এর DSU-এর মতোই vertex-গুলো পরস্পর-বিচ্ছিন্ন দলে ভাগ হয় — প্রতিটি vertex ঠিক একটি SCC-তে, আর যার কোনো সঙ্গী নেই, সে একাই একটি SCC.

এই পর্ব জুড়ে আমাদের সঙ্গী একটি কল্পিত মানচিত্র: সাতটি মোড় (0 থেকে 6) আর নয়টি একমুখী রাস্তা।

দেখুন: 1 থেকে 3-এ যাওয়া যায় (সরাসরি রাস্তা), কিন্তু 3 থেকে আর কখনো 1-এ ফেরা যায় না — B থেকে বেরোনোর একমাত্র রাস্তা 5 → 6, আর 6 একটি কানাগলি। তাই 1 আর 3 আলাদা SCC-তে। প্রতিটি vertex থেকে আলাদা করে BFS বা DFS চালিয়ে কে কার কাছে যায় তা দেখে SCC বের করা যায়, কিন্তু তাতে সময় লাগে O(V · (V + E)). এই পর্বের দুটি অ্যালগরিদম — Kosaraju আর Tarjan — একই কাজ করে মাত্র O(V + E)-এ, অর্থাৎ গ্রাফটি একবার-দুবার পড়তে যতক্ষণ লাগে ততক্ষণে। দুটিই দাঁড়িয়ে আছে পর্ব ৪১-এর DFS-এর ওপর।

পুরো পর্বে গ্রাফ রাখা হবে adjacency list-এ: প্রতিটি vertex-এর জন্য তার বের-হওয়া রাস্তাগুলোর তালিকা। আমাদের মানচিত্রে: 0: 1, 1: 2, 3, 2: 0, 6, 3: 4, 4: 5, 5: 3, 6, 6: (কিছু নেই). DFS প্রতিবেশীদের এই ক্রমেই দেখবে — ডায়াগ্রামের প্রতিটি ধাপ এই ক্রমের ওপর নির্ভর করে।

২ · Condensation — প্রতিটি SCC-কে একটি বিন্দু বানালে একটি DAG

প্রতিটি SCC-কে একটি বড় বিন্দুতে সংকুচিত করুন। দুই SCC X আর Y-এর মধ্যে X → Y edge রাখুন, যদি মূল গ্রাফে X-এর কোনো vertex থেকে Y-এর কোনো vertex-এ রাস্তা থাকে। যা পাওয়া গেল, তার নাম condensation graph. আমাদের মানচিত্রে:

   A = {0,1,2} ───────────→ B = {3,4,5}
        │     (1→3)              │
        │                        │ (5→6)
        └──────(2→6)──→ C = {6} ←┘

দাবি: যেকোনো directed গ্রাফের condensation একটি DAG (directed acyclic graph). প্রমাণ: ধরুন condensation-এ একটি cycle আছে: X₁ → X₂ → … → X_k → X₁, k ≥ 2. তাহলে X₁-এর যেকোনো vertex থেকে cycle ধরে X₂-এর যেকোনো vertex-এ যাওয়া যায় (প্রতিটি SCC-র ভেতরে সবাই সবার কাছে পৌঁছায়), আর cycle-এর বাকি অংশ ধরে আবার X₁-এ ফেরা যায়। অর্থাৎ X₁ আর X₂-এর vertex-গুলো পরস্পর reachable — তারা একই SCC-তে থাকার কথা। কিন্তু SCC মানে সবচেয়ে বড় দল, তাই এটি স্ববিরোধ। ∎

এই ছোট প্রমাণটির ফল বড়। যেকোনো directed গ্রাফ আসলে দুই স্তরের: ভেতরে কয়েকটি “ঘন” SCC, যার ভেতরে সবাই সবার কাছে যায়; আর বাইরে তাদের মধ্যে একটি DAG, যেখানে ফেরার পথ নেই। DAG-এর ওপর topological sort (পর্ব ৪২) চলে, DP চলে, সবচেয়ে লম্বা পথও সহজে বের হয়। তাই অনেক কঠিন directed-গ্রাফ সমস্যার সমাধান একই ছাঁচে: SCC বের করুন → condensation বানান → DAG-এ কাজ করুন। যেমন, “কোনো মোড় থেকে শুরু করে সর্বোচ্চ কয়টি আলাদা দোকানে যাওয়া যায়, একই মোড়ে বারবার আসা চলবে” — একটি SCC-তে ঢুকলে তার সব দোকান ঘোরা যায়, তাই প্রতিটি SCC-র দোকান যোগ করে condensation DAG-এ সবচেয়ে ভারী পথ খুঁজলেই উত্তর।

Condensation-এর দুই ধরনের বিন্দু বিশেষ গুরুত্বপূর্ণ। Source SCC: যেখানে বাইরে থেকে কোনো edge ঢোকে না (আমাদের A). Sink SCC: যেখান থেকে কোনো edge বের হয় না (আমাদের C). আমাদের মানচিত্রে 6-এ পৌঁছানো একটি রিকশা আর কোথাও যেতে পারে না — sink. দুটি অ্যালগরিদমই আসলে এই source আর sink-কে চতুরভাবে খুঁজে বের করে।

৩ · Kosaraju — দুইবার DFS, দ্বিতীয়বার উল্টো রাস্তায়

মূল ভাবনাটি এই: যদি আমরা একটি sink SCC-র কোনো vertex থেকে DFS শুরু করতে পারি, তাহলে DFS শুধু সেই SCC-র ভেতরেই ঘুরবে — বেরোনোর রাস্তা নেই — আর ঠিক সেই SCC-টিকেই দেখাবে। তারপর সেটি সরিয়ে রাখলে পরের sink খুঁজে আবার একই কাজ। সমস্যা একটাই: sink SCC-র vertex কোনটি, তা আগে থেকে জানি না।

এখানে আসে DFS-এর finish time: একটি vertex-এর সব প্রতিবেশী দেখা শেষ করে যে মুহূর্তে DFS তার থেকে ফিরে আসে। যে vertex সবচেয়ে দেরিতে শেষ হয়, সে সবসময় একটি source SCC-তে থাকে (প্রমাণ একটু পরে)। Source চাই না, sink চাই — তাই চালাকি: সব রাস্তার দিক উল্টে দিন। উল্টানো গ্রাফকে বলে transpose graph G^T. G^T-এর SCC-গুলো G-এর SCC-র হুবহু সমান (প্রতিটি পথ উল্টে দিলেও পরস্পর reachable থাকে), কিন্তু G-এর source SCC হয়ে যায় G^T-এর sink. এটিই Kosaraju-র অ্যালগরিদম:

Pseudocode — Kosaraju (0-based)

order = []                                   // pass 1: finish order on G
for each vertex u: if not seen[u]: dfs1(u)
dfs1(u): seen[u] = true
         for v in adj[u]: if not seen[v]: dfs1(v)
         order.append(u)                     // u finishes now

build GT: for each edge u -> v add v -> u    // pass 2 on the reversed graph
for u in reversed(order):                    // latest finish first
    if comp[u] == none: c = c + 1; dfs2(u, c)
dfs2(u, c): comp[u] = c
            for v in radj[u]: if comp[v] == none: dfs2(v, c)

আমাদের মানচিত্রে দুই পাস চালিয়ে দেখুন:

কেন কাজ করে — finish time-এর মূল লেমা

একটি SCC X-এর জন্য f(X) = X-এর সব vertex-এর মধ্যে সবচেয়ে বড় finish time. লেমা: G-তে দুটি আলাদা SCC X আর Y, আর X থেকে Y-তে একটি edge থাকলে f(X) > f(Y).

প্রমাণ: দুই ক্ষেত্র। (ক) DFS প্রথমে X-এ ঢোকে, ধরুন vertex x-এ। তখন X আর Y-এর সব vertex অদেখা, আর x থেকে সবাই reachable (X-এর ভেতরে, তারপর X → Y edge ধরে Y-তে). DFS-এর একটি মৌলিক বৈশিষ্ট্য (পর্ব ৪১-এর “white path” নীতি): x শেষ হওয়ার আগেই x থেকে অদেখা পথে যাওয়া যায় এমন সবাই দেখা ও শেষ হয়। তাই x সবার পরে শেষ হয়, f(X) = x-এর finish > f(Y). (খ) DFS প্রথমে Y-তে ঢোকে। Y থেকে X-এ কোনো পথ নেই — থাকলে X → Y edge-এর সাথে মিলে X আর Y একই SCC হতো। তাই Y-র সব vertex শেষ হয়ে যায় X-এর কেউ দেখা হওয়ার আগেই, f(Y) < f(X). ∎

এবার দ্বিতীয় পাস। সবচেয়ে বড় finish-এর vertex যে SCC-তে, ধরুন X, তার f(X) সবার বড় — তাই লেমা অনুযায়ী G-তে কোনো SCC থেকে X-এ edge ঢোকে না: X একটি source. GT-তে তাই X থেকে কোনো edge বের হয় না, আর GT-তে DFS ঠিক X-কেই দেখায়। পরের DFS যে SCC থেকে শুরু হয়, তার থেকে GT-তে বের-হওয়া edge শুধু এমন SCC-তে যায় যাদের f আরও বড় — অর্থাৎ যারা আগেই নেওয়া হয়ে গেছে। Induction-এ প্রতিটি দ্বিতীয়-পাসের DFS tree ঠিক একটি SCC. ∎

জটিলতা: দুটি DFS, প্রতিটি প্রতিটি vertex আর edge একবার করে ছোঁয় — O(V + E). GT বানাতেও O(V + E). বাড়তি জায়গা O(V + E) (GT-র জন্য) আর O(V) (seen, order, comp). Adjacency matrix-এ রাখলে প্রতিটি DFS O(V²).

৪ · Tarjan — এক DFS-এ low-link আর একটি stack

Kosaraju সুন্দর, কিন্তু গ্রাফটি দুবার পড়ে আর একটি উল্টো কপি বানায়। ১৯৭২ সালে Robert Tarjan একটিমাত্র DFS-এ SCC বের করার পদ্ধতি দেন। এর জন্য DFS-এর দুটি সংখ্যা লাগে:

• disc[u]: DFS কত নম্বরে u-তে প্রথম পৌঁছাল (0, 1, 2, …)।
• low[u]: u-র DFS tree-এর subtree থেকে tree edge ধরে নেমে, তারপর একটি অ-tree edge দিয়ে এখনো stack-এ থাকা কোন vertex-এ পৌঁছানো যায় — তাদের মধ্যে সবচেয়ে ছোট disc.

সাথে একটি stack: DFS যে vertex-এ ঢোকে, তাকে stack-এ রাখে; কেউ বের হয় শুধু তখন, যখন তার পুরো SCC পাওয়া যায়। মূল পর্যবেক্ষণ: প্রতিটি SCC-র যে vertex-এ DFS সবার আগে ঢোকে, সে-ই সেই SCC-র “মাথা” (root), আর SCC-র বাকি সবাই DFS tree-তে তার নিচে। মাথাকে চেনার উপায় — low[u] == disc[u]: u-র subtree থেকে u-র চেয়ে পুরোনো কোনো stack-এর vertex-এ ফেরা যায় না। তখন stack-এ u আর তার ওপরে যারা আছে, তারাই u-র SCC.

Pseudocode — Tarjan's SCC (0-based, timer starts at 0)

dfs(u):
    disc[u] = low[u] = timer++;  push u;  onStack[u] = true
    for v in adj[u]:
        if disc[v] == none:  dfs(v);  low[u] = min(low[u], low[v])   // tree edge
        else if onStack[v]:  low[u] = min(low[u], disc[v])           // edge into the open SCC
        // else: v already belongs to a finished SCC, ignore the edge
    if low[u] == disc[u]:                                            // u is the head of an SCC
        pop w until w == u, each popped w gets onStack[w] = false  -> one SCC

onStack-এর শর্তটিই অ্যালগরিদমের প্রাণ। v যদি আগেই দেখা কিন্তু এখন stack-এ না থাকে, তাহলে v একটি শেষ হয়ে যাওয়া SCC-র সদস্য — সেখান থেকে u-তে ফেরার পথ নেই (থাকলে v-র SCC তখনো শেষ হতো না)। এমন edge (প্রায়ই একটি cross edge) low-কে ছোট করলে দুটি আলাদা SCC ভুল করে জুড়ে যেত। একই মানচিত্রে চালিয়ে দেখুন:

কেন ঠিক — একটি অনানুষ্ঠানিক প্রমাণ

(১) একটি SCC-র সবাই এক সাথে বের হয়। SCC S-এর প্রথম দেখা vertex h. DFS-এর white path নীতিতে S-এর বাকি সবাই h-এর subtree-তে আসে, আর h শেষ হওয়ার আগে কেউ stack থেকে বের হয় না, যদি না তাদের নিজেদের low == disc হয়। কিন্তু S-এর কোনো r ≠ h-এর জন্য low[r] < disc[r]: r থেকে S-এর ভেতরে h-এ ফেরার পথ আছে, আর সেই পথের প্রথম যে edge r-এর subtree থেকে বেরোয়, তা stack-এ থাকা কোনো পুরোনো vertex-এ যায়। (২) h-কে চেনা যায়: h-এর subtree থেকে h-এর চেয়ে পুরোনো stack-এর vertex-এ পৌঁছানো গেলে সেই vertex আর h পরস্পর reachable হতো, অর্থাৎ h S-এর প্রথম দেখা vertex নয় — স্ববিরোধ; তাই low[h] = disc[h]. (৩) h-এর ওপরে stack-এ যারা আছে, তারা h-এর subtree-র এমন vertex যাদের SCC এখনো শেষ হয়নি — তারা h-এ ফিরতে পারে, তাই S-এর সদস্য। ∎

জটিলতা: প্রতিটি vertex একবার push, একবার pop; প্রতিটি edge একবার দেখা — O(V + E) সময়। বাড়তি জায়গা O(V): disc, low, onStack, stack আর recursion-এর গভীরতা — উল্টো গ্রাফ লাগে না।

৫ · কোড আর জটিলতা — Tarjan-এর SCC, C++ ও Python-এ

ওপরের মানচিত্রটিই কোডে: adjacency list হুবহু একই, তাই আউটপুট ডায়াগ্রামের সাথে মিলিয়ে দেখতে পারবেন। প্রতিটি SCC যে ক্রমে stack থেকে বের হয়, সেই ক্রমেই ছাপা হবে, শেষে disc আর low অ্যারে।

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> adj = {{1}, {2, 3}, {0, 6}, {4}, {5}, {3, 6}, {}};   // one-way streets: u -> v
int n = adj.size(), timer = 0;
vector<int> disc(n, -1), low(n), st;
vector<bool> onStack(n);
vector<vector<int>> comps;
void dfs(int u) {
    disc[u] = low[u] = timer++;
    st.push_back(u); onStack[u] = true;
    for (int v : adj[u]) {
        if (disc[v] == -1) { dfs(v); low[u] = min(low[u], low[v]); }   // tree edge
        else if (onStack[v]) low[u] = min(low[u], disc[v]);           // edge into the open SCC
    }
    if (low[u] == disc[u]) {                                           // u is the head of an SCC
        comps.emplace_back();
        int w;
        do { w = st.back(); st.pop_back(); onStack[w] = false; comps.back().push_back(w); } while (w != u);
    }
}
void show(const char* label, const vector<int>& a) {
    cout << label; for (int x : a) cout << ' ' << x; cout << '\n';
}
int main() {
    for (int u = 0; u < n; ++u) if (disc[u] == -1) dfs(u);
    for (size_t i = 0; i < comps.size(); ++i) { cout << "SCC " << i + 1 << ':'; show("", comps[i]); }
    show("disc:", disc);
    show("low: ", low);
}

SCC 1: 6
SCC 2: 5 4 3
SCC 3: 2 1 0
disc: 0 1 2 4 5 6 3
low:  0 0 0 4 4 4 3

from itertools import count

adj = [[1], [2, 3], [0, 6], [4], [5], [3, 6], []]   # one-way streets: u -> v
n = len(adj)
disc, low = [-1] * n, [0] * n
on_stack, stack, comps = [False] * n, [], []
tick = count()

def dfs(u):
    disc[u] = low[u] = next(tick)
    stack.append(u)
    on_stack[u] = True
    for v in adj[u]:
        if disc[v] == -1:                 # tree edge
            dfs(v)
            low[u] = min(low[u], low[v])
        elif on_stack[v]:                 # edge into the SCC still being built
            low[u] = min(low[u], disc[v])
    if low[u] == disc[u]:                 # u is the head of an SCC
        comp = []
        while True:
            w = stack.pop()
            on_stack[w] = False
            comp.append(w)
            if w == u:
                break
        comps.append(comp)

for u in range(n):
    if disc[u] == -1:
        dfs(u)
for i, comp in enumerate(comps, 1):
    print(f"SCC {i}:", *comp)
print("disc:", *disc)
print("low: ", *low)

SCC 1: 6
SCC 2: 5 4 3
SCC 3: 2 1 0
disc: 0 1 2 4 5 6 3
low:  0 0 0 4 4 4 3

৬ · প্রয়োগ — 2-SAT, বৃত্তাকার নির্ভরতা আর বন্ধুদের দল

2-SAT — শর্ত মেনে হ্যাঁ/না ঠিক করা

তিন বন্ধু — রাফি (a), মিম (b), তানিম (c) — কে কে একটি পিকনিকে যাবে, তা ঠিক করতে হবে। শর্তগুলো:

1. রাফি বা মিম, অন্তত একজন যাবে: (a ∨ b)
2. রাফি গেলে তানিমও যাবে: (¬a ∨ c)
3. মিম আর তানিম একসাথে যাবে না: (¬b ∨ ¬c)
4. তানিম আর রাফি একসাথে যাবে না: (¬c ∨ ¬a)

প্রতিটি চলক true (যাবে) বা false (যাবে না). x বা ¬x — প্রতিটিকে বলে একটি literal. শর্তগুলো AND দিয়ে জোড়া, প্রতিটি শর্তে দুটি literal-এর OR — এই রূপের নাম CNF, আর প্রতি শর্তে ঠিক দুটি literal হলে সমস্যাটি 2-SAT. সাধারণ SAT, এমনকি প্রতি শর্তে তিনটি literal-এর 3-SAT-ও NP-complete (পর্ব ৬৪) — কিন্তু 2-SAT রৈখিক সময়ে সমাধান হয়, SCC দিয়ে।

চাবিকাঠি: একটি শর্ত (x ∨ y) আসলে দুটি “যদি-তাহলে”: x মিথ্যা হলে y সত্য হতেই হবে (¬x → y), আর y মিথ্যা হলে x সত্য (¬y → x). প্রতিটি literal-কে একটি vertex বানিয়ে প্রতিটি শর্ত থেকে এই দুটি edge দিলে পাওয়া যায় implication graph — n টি চলকে 2n টি vertex, m টি শর্তে 2m টি edge. একটি পথ x ⇝ y মানে “x সত্য হলে y-কেও সত্য হতে হবে” — implication-গুলো শিকলের মতো জোড়া লাগে।

কেন উপপাদ্যটি সত্য. প্রয়োজনীয়তা: x আর ¬x একই SCC-তে থাকলে x ⇝ ¬x আর ¬x ⇝ x দুটি পথই আছে; x = true হলে প্রথম পথ ¬x-কে true করতে বাধ্য করে, x = false হলে দ্বিতীয় পথ x-কে — দুটোই অসম্ভব। যথেষ্টতা: topological ক্রমে প্রতিটি SCC-র অবস্থান t(·). নিয়ম: x = true যদি t(x) > t(¬x). ধরুন কোনো শর্ত (p ∨ q) ভেঙেছে, অর্থাৎ p আর q দুটোই false. তাহলে নিয়ম অনুযায়ী t(p) < t(¬p) আর t(q) < t(¬q). আবার edge ¬p → q আর ¬q → p থেকে t(¬p) ≤ t(q) আর t(¬q) ≤ t(p) (edge সবসময় topological ক্রমে সামনে যায়, বা একই SCC-তে থাকে). জুড়ে দিলে t(p) < t(¬p) ≤ t(q) < t(¬q) ≤ t(p) — অর্থাৎ t(p) < t(p), অসম্ভব। ∎ Tarjan SCC-গুলোকে উল্টো topological ক্রমে নম্বর দেয়, তাই Tarjan দিয়ে লিখলে নিয়মটি উল্টে যায়: x = true যদি comp[x] < comp[¬x].

কোডে literal রাখার প্রচলিত কৌশল: চলক i-এর জন্য vertex 2i = x_i আর 2i + 1 = ¬x_i; তাহলে কোনো literal-এর উল্টো পাওয়া যায় এক XOR-এ, lit ^ 1. পুরো 2-SAT তাই O(n + m): গ্রাফ বানানো, একবার Tarjan, তারপর প্রতিটি চলকে একটি তুলনা। ক্লাস রুটিন বা পরীক্ষার হলের সময়সূচিতে “দুটি বিকল্পের একটি” ধরনের সিদ্ধান্ত, মানচিত্রে নাম বসানোর কিছু মডেল, বা দুই রঙে ভাগাভাগির শর্ত — এমন অনেক সমস্যা 2-SAT-এ নামানো যায়।

বৃত্তাকার নির্ভরতা খোঁজা

একটি সফটওয়্যার প্রজেক্টে মডিউলগুলো একে অন্যকে import করে; একটি dependency graph-এ edge A → B মানে “A চলতে B লাগে”. Build করতে হলে topological ক্রম লাগে (পর্ব ৪২), আর তা সম্ভব শুধু যদি গ্রাফটি DAG হয়। Cycle থাকলে কম্পাইলার বা প্যাকেজ ম্যানেজার শুধু বলে “circular dependency” — কিন্তু কোন মডিউলগুলো এর জন্য দায়ী? উত্তর: একাধিক সদস্যের প্রতিটি SCC একটি জট, যার ভেতরের সবাই একে অন্যের ওপর ঘুরে-ফিরে নির্ভরশীল; জট ছাড়াতে প্রতিটি SCC-র ভেতরের অন্তত একটি edge ভাঙতে হবে। সাবধান: একটি vertex-এর নিজের দিকে edge (u → u, self-loop) থাকলেও সেটি cycle, যদিও SCC-তে সে একা।

একই প্রশ্ন অপারেটিং সিস্টেমে: process P1 অপেক্ষা করছে P2-র হাতে থাকা resource-এর জন্য, P2 অপেক্ষা করছে P3-র জন্য, আর P3 P1-এর জন্য — deadlock. “কে কার জন্য অপেক্ষা করছে” গ্রাফে (wait-for graph) একাধিক সদস্যের SCC মানেই এমন একটি চক্র। Spreadsheet-এ “এই ঘরের সূত্র ওই ঘরের ওপর নির্ভর করে” গ্রাফেও একই কথা — circular reference-এর সতর্কবার্তা আসলে একটি cycle খুঁজে পাওয়া।

সামাজিক নেটওয়ার্কের পরস্পর-যুক্ত দল

Facebook-এর বন্ধুত্ব দুদিকের (undirected), কিন্তু “follow” একদিকের — আপনি একজন ক্রিকেটারকে follow করেন, তিনি আপনাকে করেন না। Follow-গ্রাফের একটি SCC এমন একদল মানুষ, যাদের যেকোনো একজনের পোস্ট share-এর শিকল ধরে দলের যেকোনো জনের কাছে পৌঁছাতে পারে — আর ফিরেও আসতে পারে। বাস্তব বড় নেটওয়ার্কে সাধারণত একটি বিশাল SCC থাকে, আর তার চারপাশে অনেক ছোট ছোট দল আর একা মানুষ। ওয়েবের লিংক-গ্রাফেও একই ধাঁচ দেখা গেছে (প্রশ্ন ০৩). সুপারিশ (recommendation) বা গুজব কতদূর ছড়াবে — এমন বিশ্লেষণের প্রথম ধাপ প্রায়ই এই SCC-ভাগ।

৭ · নেটওয়ার্কের দুর্বল জায়গা — bridge আর articulation point

এবার দিক ছাড়া, অর্থাৎ undirected গ্রাফ। একটি ইন্টারনেট সেবাদাতার আটটি router (0 থেকে 7) আর দশটি কেবল। প্রকৌশলীর প্রশ্ন: কোন একটি কেবল কাটা পড়লে নেটওয়ার্ক দুই টুকরো হয়ে যাবে? আর কোন একটি router বিকল হলে? প্রথম ধরনের edge-কে বলে bridge (cut edge), দ্বিতীয় ধরনের vertex-কে articulation point (cut vertex). সংজ্ঞা: যাকে সরালে connected component-এর সংখ্যা বাড়ে।

ছবি দেখে বলা সহজ: 1–3 কেবল কাটলে বাঁয়ের ত্রিভুজ আলাদা; router 4 বিকল হলে 6 আর 7 বিচ্ছিন্ন। কিন্তু 6–7? সেখানে দুটি কেবল — একটি কাটলেও অন্যটি আছে, তাই 6–7 bridge নয়. তবু router 6 বিকল হলে 7 একা হয়ে যায় — 6 একটি articulation point. প্রতিটি edge বা vertex একে একে সরিয়ে BFS চালালে O(E · (V + E)) বা O(V · (V + E)) সময়; আমরা চাই এক DFS-এ, O(V + E)-এ।

Undirected DFS-এর একটি উপহার — cross edge নেই

Undirected গ্রাফে DFS চালালে প্রতিটি edge হয় tree edge, নয় back edge — কোনো edge দুটি আলাদা শাখাকে জোড়ে না। কারণ: u-তে থাকার সময় কোনো প্রতিবেশী v অদেখা থাকলে DFS তাকে u-এর subtree-তেই ঢুকিয়ে নেয়। তাই একটি subtree থেকে বাইরে যাওয়ার একমাত্র উপায় হলো কোনো back edge দিয়ে ওপরের দিকে, পূর্বপুরুষের কাছে ওঠা। low[v] ঠিক এটাই মাপে: v-র subtree থেকে একটি back edge দিয়ে সবচেয়ে ওপরের (ছোট disc-এর) কোন vertex-এ ওঠা যায়।

পার্থক্যটি মাত্র একটি সমান চিহ্ন, তাই মনে রাখার উপায়: bridge-এর জন্য v-র subtree-কে edge-টি ছাড়া u-তে পৌঁছাতে পারলেই চলে (low[v] ≤ disc[u] হলে bridge নয়); articulation point-এর জন্য u নিজেই সরে যায়, তাই u-তে পৌঁছানো যথেষ্ট নয় — u-র ওপরে উঠতে হবে (low[v] < disc[u] হলে তবেই নিরাপদ)। Root-এর জন্য আলাদা নিয়ম কেন লাগে? Root-এর ওপরে কেউ নেই, তাই প্রতিটি child-এর জন্য low[v] ≥ disc[root] = 0 সবসময় সত্য — সাধারণ শর্ত বসালে প্রতিটি root ভুল করে articulation point হয়ে যেত।

Multi-edge সামলানো. Low হিসাবের সময় parent-এ ফেরার edge-টি বাদ দিতে হয়, নইলে প্রতিটি v সেই tree edge দিয়েই u-তে “ফিরে” low[v] ≤ disc[u] বানাত, আর কোনো bridge পাওয়া যেত না। অনেকে বাদ দেন “parent vertex”-কে — কিন্তু multigraph-এ, যেখানে 6 আর 7-এর মধ্যে দুটি কেবল, তাতে দ্বিতীয় কেবলটিও বাদ পড়ে আর 6–7 ভুল করে bridge হয়ে যায়। সঠিক উপায়: প্রতিটি edge-কে একটি id দিন, আর বাদ দিন শুধু যে edge দিয়ে এসেছেন, সেই id-কে।

প্রমাণের সারকথা (bridge). Tree edge (u, v) কাটলে v-র subtree T_v বাকি গ্রাফের সাথে যুক্ত থাকে শুধু তখন, যখন T_v-এর বাইরে যাওয়ার অন্য কোনো edge আছে। Cross edge নেই, তাই এমন edge মানে T_v থেকে u বা তার কোনো পূর্বপুরুষে যাওয়া একটি back edge — যার অস্তিত্ব ঠিক low[v] ≤ disc[u]-এর সমান। তাই bridge ⇔ low[v] > disc[u]. Articulation point-এর যুক্তি একই, শুধু u নিজে সরে যায় বলে u-তে পৌঁছানো back edge আর কাজে আসে না: শর্তটি হয় low[v] ≥ disc[u]. ∎

৮ · কোড, biconnected component আর বাস্তবের নেটওয়ার্ক

ওপরের নেটওয়ার্কটি কোডে, edge-গুলো id-সহ। Adjacency list-এ প্রতিটি প্রতিবেশীর সাথে edge-এর id রাখা হয়েছে, আর DFS মনে রাখে কোন id দিয়ে সে এসেছে।

#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
int n = 8, timer = 0;
vector<pair<int, int>> edges = {{0, 1}, {1, 2}, {2, 0}, {1, 3}, {3, 4}, {4, 5}, {5, 3}, {4, 6}, {6, 7}, {6, 7}};
vector<vector<pair<int, int>>> adj(n);            // (neighbour, edge id)
vector<int> disc(n, -1), low(n);
vector<bool> isCut(n);
vector<pair<int, int>> bridges;
void dfs(int u, int parentEdge) {
    disc[u] = low[u] = timer++; int children = 0;
    for (auto [v, id] : adj[u]) {
        if (id == parentEdge) continue;                // skip only the edge we came by
        if (disc[v] != -1) { low[u] = min(low[u], disc[v]); continue; }   // back edge
        ++children;                                    // tree edge
        dfs(v, id);
        low[u] = min(low[u], low[v]);
        if (low[v] > disc[u]) bridges.push_back({u, v});
        if (parentEdge != -1 && low[v] >= disc[u]) isCut[u] = true;
    }
    if (parentEdge == -1 && children > 1) isCut[u] = true;   // root rule
}
int main() {
    for (int i = 0; i < (int)edges.size(); ++i) { auto [a, b] = edges[i]; adj[a].push_back({b, i}); adj[b].push_back({a, i}); }
    for (int u = 0; u < n; ++u) if (disc[u] == -1) dfs(u, -1);
    cout << "bridges:";
    for (size_t i = 0; i < bridges.size(); ++i) cout << (i ? ", " : " ") << bridges[i].first << '-' << bridges[i].second;
    cout << "\narticulation points:";
    for (int u = 0; u < n; ++u) if (isCut[u]) cout << ' ' << u;
    cout << "\nlow:"; for (int x : low) cout << ' ' << x;
    cout << '\n';
}

bridges: 4-6, 1-3
articulation points: 1 3 4 6
low: 0 0 0 3 3 3 6 6

from itertools import count

n = 8
edges = [(0, 1), (1, 2), (2, 0), (1, 3), (3, 4), (4, 5), (5, 3), (4, 6), (6, 7), (6, 7)]
adj = [[] for _ in range(n)]
for i, (a, b) in enumerate(edges):        # store (neighbour, edge id)
    adj[a].append((b, i))
    adj[b].append((a, i))
disc, low = [-1] * n, [0] * n
is_cut, bridges = [False] * n, []
tick = count()

def dfs(u, parent_edge):
    disc[u] = low[u] = next(tick)
    children = 0
    for v, eid in adj[u]:
        if eid == parent_edge: continue   # skip only the edge we came by, not a parallel one
        if disc[v] != -1:                 # back edge
            low[u] = min(low[u], disc[v])
            continue
        children += 1                     # tree edge
        dfs(v, eid)
        low[u] = min(low[u], low[v])
        if low[v] > disc[u]:
            bridges.append((u, v))
        if parent_edge != -1 and low[v] >= disc[u]:
            is_cut[u] = True
    if parent_edge == -1 and children > 1:   # root rule
        is_cut[u] = True
for u in range(n):
    if disc[u] == -1:
        dfs(u, -1)
print("bridges:", ", ".join(f"{a}-{b}" for a, b in bridges))
print("articulation points:", *[u for u in range(n) if is_cut[u]])
print("low:", *low)

bridges: 4-6, 1-3
articulation points: 1 3 4 6
low: 0 0 0 3 3 3 6 6

Biconnected আর 2-edge-connected component — সংক্ষেপে

Bridge আর articulation point গ্রাফকে “শক্ত টুকরো”-য় ভাগ করে। দুই ধরনের ভাগ আছে:

• 2-edge-connected component: সব bridge মুছে ফেললে যে component-গুলো থাকে। আমাদের নেটওয়ার্কে {0, 1, 2}, {3, 4, 5}, {6, 7}. প্রতিটির ভেতরে যেকোনো একটি কেবল কাটলেও সবাই যুক্ত। Vertex-গুলো এতে ভাগ হয়। প্রতিটিকে একটি বিন্দু বানালে bridge-গুলোই edge হয়ে একটি bridge tree তৈরি করে — এখানে একটি শিকল: {0,1,2} — {3,4,5} — {6,7}.
• Biconnected component (block): articulation point ছাড়া সবচেয়ে বড় টুকরো, যেখানে যেকোনো একটি router বিকল হলেও বাকিরা যুক্ত। এখানে edge-গুলো ভাগ হয়, আর articulation point একাধিক block-এ থাকে: {0,1,2}, {1,3}, {3,4,5}, {4,6}, {6,7} (দুটি কেবলসহ) — পাঁচটি block. Block আর articulation point দিয়ে বানানো block-cut tree দেখায় কোন router কোন অংশগুলোকে ধরে রেখেছে।

দুটোই একই DFS-এ বের হয়। Biconnected component-এর জন্য একটি edge-এর stack রাখুন: প্রতিটি tree edge আর back edge push করুন; যখন child v-এর জন্য low[v] ≥ disc[u], তখন stack থেকে (u, v) পর্যন্ত সব edge pop — সেটি একটি block. ঠিক Tarjan-এর SCC-র stack-কৌশল, শুধু vertex-এর বদলে edge. মোট সময় আবার O(V + E).

৯ · AI-এর যুগে SCC আর bridge — সুন্দর কোড, সূক্ষ্ম ভুল

“Tarjan-এর SCC লিখে দাও” বা “bridges in a graph” — AI সহকারী মুহূর্তে চল্লিশ লাইন দেবে, আর ছোট উদাহরণে তা প্রায়ই ঠিক উত্তরও দেবে। ভুলগুলো লুকিয়ে থাকে ঠিক সেই জায়গায়, যেখানে এই পর্বে সময় দিয়েছি: onStack-এর শর্ত, parent edge বনাম parent vertex, root-এর নিয়ম, > বনাম ≥. এসব ভুল সাধারণ টেস্টে ধরা পড়ে না — ধরা পড়ে শুধু বিশেষ গঠনের গ্রাফে।

এই বিষয়ে AI সাধারণত যেসব ভুল করে

কোড যাচাইয়ের চেকলিস্ট

• ছোট গ্রাফে disc, low আর stack হাতে trace করে কোডের আউটপুটের সাথে মিলিয়েছি
• একটি brute force লিখেছি — প্রতিটি জোড়ায় দুই দিকে BFS দিয়ে SCC, প্রতিটি edge/vertex সরিয়ে component গুনে bridge/articulation point
• শত শত এলোমেলো ছোট গ্রাফে দুটির উত্তর মিলিয়েছি — stress testing, multi-edge আর self-loop-সহ
• Edge case: একটি vertex, কোনো edge নেই, disconnected গ্রাফ, পুরো গ্রাফ একটি cycle, একটি লম্বা শিকল
• বড় ইনপুটে recursion-এর গভীরতা পরীক্ষা করেছি; দরকারে iterative DFS
• 2-SAT-এ পাওয়া মান দিয়ে প্রতিটি clause আলাদা করে পরীক্ষা করেছি