Strongly Connected Components
স্ট্রংলি কানেক্টেড কম্পোনেন্ট
Directed graph-এর এমন maximal অংশ যেখানে যেকোনো node থেকে বাকি সব node-এ যাওয়া যায় — Kosaraju বা Tarjan DFS দিয়ে O(V+E)-তে বের হয়।
also: scc, strongly connected component
প্রতিটা SCC-কে এক super-node ধরলে যে graph পাওয়া যায় (condensation) সেটা DAG — তাই SCC বের করাই dependency cycle-এর গোছানো map।
Kosaraju-র দুই পাস:
- G-তে DFS চালিয়ে finish time অনুযায়ী order বানাও
- Reversed graph-এ সেই order-এর উল্টো দিকে DFS — প্রতি tree = এক SCC
Tarjan single pass-এই করে — stack আর low-link value দিয়ে।
ব্যবহার: package dependency-র circular group, compiler-এ call graph, web-এ page cluster, 2-SAT solution — সব SCC-র কাজ।