স্ট্রংলি কানেক্টেড কম্পোনেন্ট — টার্জান ও কোসারাজু

def kosaraju_scc(graph, vertices):
    visited = set()
    finish_order = []

    def dfs_pass1(start):
        stack = [(start, iter(graph.get(start, [])))]
        visited.add(start)
        while stack:
            node, neighbors = stack[-1]
            advanced = False
            for v in neighbors:
                if v not in visited:
                    visited.add(v)
                    stack.append((v, iter(graph.get(v, []))))
                    advanced = True
                    break
            if not advanced:
                finish_order.append(node)
                stack.pop()

    for v in vertices:
        if v not in visited:
            dfs_pass1(v)

    reverse_graph = {v: [] for v in vertices}
    for u in vertices:
        for v in graph.get(u, []):
            reverse_graph[v].append(u)

    visited2 = set()
    components = []

    def dfs_pass2(start):
        comp = [start]
        visited2.add(start)
        stack = [start]
        while stack:
            node = stack.pop()
            for v in reverse_graph.get(node, []):
                if v not in visited2:
                    visited2.add(v)
                    comp.append(v)
                    stack.append(v)
        return comp

    for v in reversed(finish_order):
        if v not in visited2:
            components.append(dfs_pass2(v))

    return components

def reachable_set(graph, source, vertices):
    # সম্পূর্ণ স্বাধীন সরল DFS -- কোসারাজুর কোনো ধারণা (ফিনিশ অর্ডার, রিভার্স গ্রাফ) ব্যবহার করে না
    visited = {source}
    stack = [source]
    while stack:
        u = stack.pop()
        for v in graph.get(u, []):
            if v not in visited:
                visited.add(v)
                stack.append(v)
    return visited

def verify_sccs_bruteforce(graph, vertices, components):
    reach = {v: reachable_set(graph, v, vertices) for v in vertices}
    ok = True
    # চেক ১: একই দাবিকৃত SCC-এর ভেতরে প্রতিটি জোড়া মিউচুয়ালি রিচেবল হতেই হবে
    for comp in components:
        for u in comp:
            for v in comp:
                if v not in reach[u] or u not in reach[v]:
                    ok = False
                    print(f"  FAIL: {u} ও {v} মিউচুয়ালি রিচেবল নয় কিন্তু একই SCC-তে দাবি করা হয়েছে!")
    # চেক ২: ভিন্ন দাবিকৃত SCC-এর কোনো জোড়া যেন মিউচুয়ালি রিচেবল না হয়
    for i in range(len(components)):
        for j in range(len(components)):
            if i == j:
                continue
            u = components[i][0]
            for v in components[j]:
                if v in reach[u] and u in reach[v]:
                    ok = False
                    print(f"  FAIL: {u} (SCC {i}) ও {v} (SCC {j}) মিউচুয়ালি রিচেবল কিন্তু ভিন্ন SCC-তে দাবি করা হয়েছে!")
    return ok

test_graphs = [
    {
        "name": "একাধিক সাইকেলসহ গ্রাফ (প্রত্যাশিত ৪টি SCC)",
        "vertices": list(range(8)),
        "edges": {0: [1], 1: [2], 2: [0, 3], 3: [4], 4: [5], 5: [6], 6: [4, 7], 7: []},
    },
    {
        "name": "একটি DAG (কোনো সাইকেল নেই, প্রতিটি ভার্টেক্স তার নিজস্ব SCC)",
        "vertices": [0, 1, 2, 3],
        "edges": {0: [1], 1: [2], 2: [], 3: [1]},
    },
]

for t in test_graphs:
    comps = kosaraju_scc(t["edges"], t["vertices"])
    print(f"\n{t['name']}")
    print(f"  কোসারাজুর SCC: {comps}")
    verified = verify_sccs_bruteforce(t["edges"], t["vertices"], comps)
    print(f"  ব্রুট-ফোর্স মিউচুয়াল-রিচেবিলিটি যাচাই পাস: {verified}")
    assert verified