স্ট্রংলি কানেক্টেড কম্পোনেন্ট এবং কনডেনসেশন গ্রাফ#

সংজ্ঞাসমূহ#

ধরি $G=(V,E)$ একটি ডিরেক্টেড গ্রাফ যার ভার্টেক্স $V$ এবং এজ $E \subseteq V \times V$। আমরা $n=|V|$ দিয়ে ভার্টেক্স সংখ্যা এবং $m=|E|$ দিয়ে $G$-তে এজ সংখ্যা বোঝাই। এই নিবন্ধের সব সংজ্ঞা মাল্টিগ্রাফে সম্প্রসারণ করা সহজ, তবে আমরা সেদিকে মনোযোগ দেব না।

$C \subseteq V$ ভার্টেক্সের একটি উপসেটকে স্ট্রংলি কানেক্টেড কম্পোনেন্ট বলা হয় যদি নিম্নলিখিত শর্তগুলো পূরণ হয়:

• $C$-এর সব $u,v$-এর জন্য, যদি $u \neq v$ হয় তাহলে $u$ থেকে $v$-তে একটি পাথ এবং $v$ থেকে $u$-তে একটি পাথ বিদ্যমান, এবং
• $C$ ম্যাক্সিমাল, অর্থাৎ উপরের শর্ত লঙ্ঘন না করে কোনো ভার্টেক্স যোগ করা যায় না।

আমরা $\text{SCC}(G)$ দিয়ে $G$-এর স্ট্রংলি কানেক্টেড কম্পোনেন্টগুলোর সেট বোঝাই। এই স্ট্রংলি কানেক্টেড কম্পোনেন্টগুলো পরস্পরকে ছেদ করে না এবং গ্রাফের সব ভার্টেক্স আবৃত করে। সুতরাং, $\text{SCC}(G)$ সেটটি $V$-এর একটি পার্টিশন।

এই গ্রাফ $G_\text{example}$ বিবেচনা করুন, যেখানে স্ট্রংলি কানেক্টেড কম্পোনেন্টগুলো হাইলাইট করা হয়েছে:

এখানে $\text{SCC}(G_\text{example})=\{\{0,7\},\{1,2,3,5,6\},\{4,9\},\{8\}\}.$ আমরা নিশ্চিত করতে পারি যে প্রতিটি স্ট্রংলি কানেক্টেড কম্পোনেন্টের ভেতরে সব ভার্টেক্স পরস্পরের কাছে পৌঁছানো যায়।

আমরা কনডেনসেশন গ্রাফ $G^{\text{SCC}}=(V^{\text{SCC}}, E^{\text{SCC}})$ নিম্নরূপে সংজ্ঞায়িত করি:

• $G^{\text{SCC}}$-এর ভার্টেক্স হলো $G$-এর স্ট্রংলি কানেক্টেড কম্পোনেন্ট; অর্থাৎ, $V^{\text{SCC}} = \text{SCC}(G)$, এবং
• কনডেনসেশন গ্রাফের সব ভার্টেক্স $C_i,C_j$-এর জন্য, $C_i$ থেকে $C_j$-তে একটি এজ আছে যদি এবং কেবল যদি $C_i \neq C_j$ এবং $C_i$-তে কোনো $a$ ও $C_j$-তে কোনো $b$ বিদ্যমান থাকে যেন $G$-তে $a$ থেকে $b$-তে একটি এজ থাকে।

$G_\text{example}$-এর কনডেনসেশন গ্রাফ নিম্নরূপ:

কনডেনসেশন গ্রাফের সবচেয়ে গুরুত্বপূর্ণ বৈশিষ্ট্য হলো এটি অ্যাসাইক্লিক। প্রকৃতপক্ষে, সংজ্ঞা অনুযায়ী কনডেনসেশন গ্রাফে কোনো ‘সেল্ফ-লুপ’ নেই, এবং যদি দুই বা ততোধিক ভার্টেক্সের (স্ট্রংলি কানেক্টেড কম্পোনেন্ট) মধ্য দিয়ে কোনো সাইকেল থাকত, তাহলে পৌঁছানোযোগ্যতার কারণে এই স্ট্রংলি কানেক্টেড কম্পোনেন্টগুলোর ইউনিয়ন নিজেই একটি স্ট্রংলি কানেক্টেড কম্পোনেন্ট হতো: বিরোধ।

পরবর্তী বিভাগে বর্ণিত অ্যালগরিদম একটি প্রদত্ত গ্রাফে সব স্ট্রংলি কানেক্টেড কম্পোনেন্ট খুঁজে বের করে। এরপর, কনডেনসেশন গ্রাফ তৈরি করা যায়।

কোসারাজুর অ্যালগরিদম#

অ্যালগরিদমের বর্ণনা#

বর্ণিত অ্যালগরিদমটি স্বাধীনভাবে কোসারাজু এবং শরীর ১৯৮০ সালের দিকে প্রস্তাব করেছিলেন। এটি দুটি সিরিজের ডেপথ ফার্স্ট সার্চ-এর উপর ভিত্তি করে, রানটাইম $O(n + m)$।

অ্যালগরিদমের প্রথম ধাপে, আমরা সম্পূর্ণ গ্রাফ ভিজিট করে ডেপথ ফার্স্ট সার্চের একটি ক্রম সম্পাদন করি (dfs)। অর্থাৎ, যতক্ষণ অভিজিত ভার্টেক্স আছে, আমরা তাদের একটি নিই এবং সেই ভার্টেক্স থেকে ডেপথ ফার্স্ট সার্চ শুরু করি। প্রতিটি ভার্টেক্সের জন্য, আমরা এক্সিট টাইম $t_\text{out}[v]$ ট্র্যাক রাখি। এটি সেই ‘টাইমস্ট্যাম্প’ যখন ভার্টেক্স $v$-তে dfs-এর এক্সিকিউশন শেষ হয়, অর্থাৎ $v$ থেকে পৌঁছানো সব ভার্টেক্স ভিজিট হয়ে গেছে এবং অ্যালগরিদম $v$-তে ফিরে এসেছে। টাইমস্ট্যাম্প কাউন্টার পরপর dfs কলের মধ্যে রিসেট হওয়া উচিত নয়। এক্সিট টাইম অ্যালগরিদমে গুরুত্বপূর্ণ ভূমিকা পালন করে, যা নিম্নলিখিত উপপাদ্য আলোচনা করলে স্পষ্ট হবে।

প্রথমে, আমরা একটি স্ট্রংলি কানেক্টেড কম্পোনেন্ট $C$-এর এক্সিট টাইম $t_\text{out}[C]$ সংজ্ঞায়িত করি $C$-এর সব $v$-এর $t_\text{out}[v]$ মানের সর্বোচ্চ হিসেবে। এছাড়াও, উপপাদ্যের প্রমাণে, আমরা প্রতিটি ভার্টেক্স $v\in G$-এর এন্ট্রি টাইম $t_{\text{in}}[v]$ উল্লেখ করব। $t_{\text{in}}[v]$ সংখ্যাটি সেই ‘টাইমস্ট্যাম্প’ যখন অ্যালগরিদমের প্রথম ধাপে ভার্টেক্স $v$-তে রিকার্সিভ ফাংশন dfs কল করা হয়। একটি স্ট্রংলি কানেক্টেড কম্পোনেন্ট $C$-এর জন্য, আমরা $t_{\text{in}}[C]$ সংজ্ঞায়িত করি $C$-এর সব $v$-এর $t_{\text{in}}[v]$ মানের সর্বনিম্ন হিসেবে।

যদি আমরা সব ভার্টেক্স $v \in V$-কে তাদের এক্সিট টাইম $t_\text{out}[v]$-এর নিম্নক্রমে সাজাই, তাহলে প্রথম ভার্টেক্স $u$ “রুট” স্ট্রংলি কানেক্টেড কম্পোনেন্টে থাকবে, যার কনডেনসেশন গ্রাফে কোনো ইনকামিং এজ নেই। এখন আমরা এই ভার্টেক্স $u$ থেকে এমন কোনো সার্চ চালাতে চাই যেটি তার স্ট্রংলি কানেক্টেড কম্পোনেন্টের সব ভার্টেক্স ভিজিট করবে, কিন্তু অন্য ভার্টেক্স নয়। বারবার এটি করে, আমরা ধীরে ধীরে সব স্ট্রংলি কানেক্টেড কম্পোনেন্ট খুঁজে পেতে পারি: প্রথম পাওয়া কম্পোনেন্টের সব ভার্টেক্স সরিয়ে, $t_\text{out}$-এর সবচেয়ে বড় মানের পরবর্তী অবশিষ্ট ভার্টেক্স খুঁজে সেখান থেকে এই সার্চ চালাই, এভাবে চলতে থাকবে। শেষে, আমরা সব স্ট্রংলি কানেক্টেড কম্পোনেন্ট খুঁজে পাব। আমাদের ইচ্ছামতো আচরণ করে এমন একটি সার্চ পদ্ধতি খুঁজতে, নিম্নলিখিত উপপাদ্য বিবেচনা করুন:

সুতরাং, সংক্ষেপে, আমরা স্ট্রংলি কানেক্টেড কম্পোনেন্ট খুঁজে বের করার নিম্নলিখিত অ্যালগরিদম আলোচনা করলাম:

• ধাপ ১। $G$-তে ডেপথ ফার্স্ট সার্চের একটি ক্রম চালান, যেটি ভার্টেক্সের একটি তালিকা (যেমন order) দেবে, ক্রমবর্ধমান এক্সিট টাইম $t_\text{out}$ অনুসারে সাজানো।

• ধাপ ২। ট্রান্সপোজ গ্রাফ $G^T$ তৈরি করুন, এবং বিপরীত ক্রমে (অর্থাৎ এক্সিট টাইমের নিম্নক্রমে) ভার্টেক্সগুলোতে ডেপথ ফার্স্ট সার্চের একটি সিরিজ চালান। প্রতিটি ডেপথ ফার্স্ট সার্চ একটি স্ট্রংলি কানেক্টেড কম্পোনেন্ট দেবে।

• ধাপ ৩ (ঐচ্ছিক)। কনডেনসেশন গ্রাফ তৈরি করুন।

অ্যালগরিদমের রানটাইম কমপ্লেক্সিটি $O(n + m)$, কারণ ডেপথ ফার্স্ট সার্চ দুইবার করা হয়। কনডেনসেশন গ্রাফ তৈরিও $O(n+m)$।

সবশেষে, এখানে টপোলজিক্যাল সর্ট উল্লেখ করা যথাযথ। ধাপ ১-এ, আমরা ভার্টেক্সগুলো ক্রমবর্ধমান এক্সিট টাইমের ক্রমে পাই। যদি $G$ অ্যাসাইক্লিক হয়, এটি $G$-এর একটি (বিপরীত) টপোলজিক্যাল সর্টের সাথে মিলে যায়। ধাপ ২-এ, অ্যালগরিদম স্ট্রংলি কানেক্টেড কম্পোনেন্টগুলো তাদের এক্সিট টাইমের নিম্নক্রমে খুঁজে পায়। সুতরাং, এটি কম্পোনেন্টগুলো — কনডেনসেশন গ্রাফের ভার্টেক্স — কনডেনসেশন গ্রাফের টপোলজিক্যাল সর্টের সাথে মিলে যায় এমন ক্রমে খুঁজে পায়।

ইমপ্লিমেন্টেশন#

vector<bool> visited; // keeps track of which vertices are already visited

// runs depth first search starting at vertex v.
// each visited vertex is appended to the output vector when dfs leaves it.
void dfs(int v, vector<vector<int>> const& adj, vector<int> &output) {
    visited[v] = true;
    for (auto u : adj[v])
        if (!visited[u])
            dfs(u, adj, output);
    output.push_back(v);
}

// input: adj -- adjacency list of G
// output: components -- the strongy connected components in G
// output: adj_cond -- adjacency list of G^SCC (by root vertices)
void strongly_connected_components(vector<vector<int>> const& adj,
                                  vector<vector<int>> &components,
                                  vector<vector<int>> &adj_cond) {
    int n = adj.size();
    components.clear(), adj_cond.clear();

    vector<int> order; // will be a sorted list of G's vertices by exit time

    visited.assign(n, false);

    // first series of depth first searches
    for (int i = 0; i < n; i++)
        if (!visited[i])
            dfs(i, adj, order);

    // create adjacency list of G^T
    vector<vector<int>> adj_rev(n);
    for (int v = 0; v < n; v++)
        for (int u : adj[v])
            adj_rev[u].push_back(v);

    visited.assign(n, false);
    reverse(order.begin(), order.end());

    vector<int> roots(n, 0); // gives the root vertex of a vertex's SCC

    // second series of depth first searches
    for (auto v : order)
        if (!visited[v]) {
            std::vector<int> component;
            dfs(v, adj_rev, component);
            components.push_back(component);
            int root = *component.begin();
            for (auto u : component)
                roots[u] = root;
        }

    // add edges to condensation graph
    adj_cond.assign(n, {});
    for (int v = 0; v < n; v++)
        for (auto u : adj[v])
            if (roots[v] != roots[u])
                adj_cond[roots[v]].push_back(roots[u]);
}

dfs ফাংশনটি ডেপথ ফার্স্ট সার্চ ইমপ্লিমেন্ট করে। এটি ইনপুট হিসেবে একটি অ্যাডজেসেন্সি লিস্ট এবং একটি স্টার্টিং ভার্টেক্স নেয়। এটি output ভেক্টরের একটি রেফারেন্সও নেয়: প্রতিটি ভিজিট করা ভার্টেক্স dfs সেটি ছেড়ে যাওয়ার সময় output-এ যোগ হবে।

লক্ষ্য করুন যে আমরা dfs ফাংশন অ্যালগরিদমের প্রথম এবং দ্বিতীয় উভয় ধাপেই ব্যবহার করি। প্রথম ধাপে, আমরা $G$-এর অ্যাডজেসেন্সি লিস্ট পাস করি, এবং পরপর dfs কলে আমরা একই ‘আউটপুট ভেক্টর’ order পাস করতে থাকি, যেন শেষ পর্যন্ত আমরা ক্রমবর্ধমান এক্সিট টাইমের ক্রমে ভার্টেক্সের তালিকা পাই। দ্বিতীয় ধাপে, আমরা $G^T$-এর অ্যাডজেসেন্সি লিস্ট পাস করি, এবং প্রতিটি কলে একটি খালি ‘আউটপুট ভেক্টর’ component পাস করি, যেটি আমাদের একটি করে স্ট্রংলি কানেক্টেড কম্পোনেন্ট দেবে।

টারজানের স্ট্রংলি কানেক্টেড কম্পোনেন্ট অ্যালগরিদম#

অ্যালগরিদমের বর্ণনা#

বর্ণিত অ্যালগরিদমটি প্রথম ১৯৭২ সালে টারজান প্রস্তাব করেছিলেন। এটি DFS কলের একটি ক্রম সম্পাদনের উপর ভিত্তি করে, এর গঠনের অন্তর্নিহিত তথ্য ব্যবহার করে স্ট্রংলি কানেক্টেড কম্পোনেন্ট (এসসিসি) নির্ধারণ করে, রানটাইম $O(n+m)$।

একটি ভার্টেক্সে DFS প্রয়োগ করার সময়, আমরা তার অ্যাডজেসেন্সি লিস্ট ট্রাভার্স করব, এবং যদি কোনো অভিজিত ভার্টেক্স পাই, আমরা রিকার্সিভভাবে সেটিতে DFS প্রয়োগ করব।

আসুন DFS কলের ক্রম দ্বারা উদ্ভূত ট্রি বিবেচনা করি, যেটিকে আমরা DFS ট্রি বলব। একটি এসসিসি-র কোনো ভার্টেক্সে প্রথম DFS কল করলে, সেই কল শেষ হওয়ার আগেই তার এসসিসি-র সব ভার্টেক্স ভিজিট হবে, কারণ তারা সবাই পরস্পরের কাছে পৌঁছানো যায়। DFS ট্রি-তে, এই প্রথম ভার্টেক্সটি এসসিসি-র অন্য সব ভার্টেক্সের কমন অ্যানসেস্টর হবে; আমরা এই ভার্টেক্সকে এসসিসি-র রুট হিসেবে সংজ্ঞায়িত করি।

অ্যালগরিদমের ধারণা নিম্নরূপ:

• আমরা DFS কলের একটি ক্রম সম্পাদন করি, অ্যাডজেসেন্সি লিস্টের ভার্টেক্সগুলোতে রিকার্সিভভাবে প্রয়োগ করি।

• একটি ভার্টেক্সের অ্যাডজেসেন্সি লিস্ট ট্রাভার্স শেষ হলে, আমরা কোনোভাবে নির্ধারণ করতে পারি এটি রুট কি না। এই পদ্ধতি পরে ব্যাখ্যা করা হবে।

• ভার্টেক্সটি রুট হলে, আমরা তৎক্ষণাৎ তার এসসিসি-র সব ভার্টেক্স খুঁজে বের করব এবং দাবি করব।

সব কল শেষ হলে, সব রুট শনাক্ত হয়ে যাবে এবং সব ভার্টেক্স কোনো না কোনো এসসিসি-র অংশ হিসেবে দাবি করা হয়ে যাবে।

আসুন এখন এই দাবি করার প্রক্রিয়া প্রবর্তন করলে DFS-এর বৈশিষ্ট্যগুলো বিশ্লেষণ করি।

ধরি $v$ একটি ভার্টেক্স এবং তার সাবট্রি বিবেচনা করি। তার অ্যাডজেসেন্সি লিস্ট ট্রাভার্স শেষ করার সময়ে, সাবট্রি-র বাইরে DFS দ্বারা ইতোমধ্যে ভিজিত যেকোনো ভার্টেক্সের $t_{in}$ মান ছোট হবে, কারণ $v$-তে শুরু হওয়ার আগেই তাদের উপর DFS কল করা হয়েছিল।

দাবি করার প্রক্রিয়া বিবেচনা করলে, $v$-এর সাবট্রি-র বাইরে সব অদাবিকৃত ভার্টেক্সের $t_{in}$ মান $t_{in}[v]$ থেকে ছোট। এখন আমরা দেখতে পাচ্ছি কীভাবে $t_{in}$ ব্যবহার করে রুট নির্ধারণ করা যায়। আমরা পৌঁছাতে পারা অদাবিকৃত ভার্টেক্সগুলোর $t_{in}$-এর সর্বনিম্ন মান বিবেচনা করি এবং ট্রি-এজের মাধ্যমে এই তথ্য অ্যানসেস্টরদের কাছে প্রচার করি। প্রচারিত মানকে আমরা $t_{low}$ বলব।

আরো আনুষ্ঠানিকভাবে, আমরা $t_{low}[v]$-কে সংজ্ঞায়িত করি $v$-এর সাবট্রি-র কোনো ভার্টেক্স থেকে সরাসরি এজের মাধ্যমে পৌঁছানো যায় এমন সর্বনিম্ন $t_{in}$ মান হিসেবে। তাই আমরা $t_{low}[v] < t_{in}[v]$ পরীক্ষা করে একটি ভার্টেক্স $v$ রুট কি না শনাক্ত করতে পারি।

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

• যখন আমরা প্রথম একটি ভার্টেক্স ভিজিট করি, আমাদের শুধু এটি ডেটা স্ট্রাকচারে ইনসার্ট করতে হবে, কারণ এই ভার্টেক্স অদাবিকৃত।

• যখন আমরা একটি রুট পাই, আমাদের তার সাবট্রি-র সব অবশিষ্ট অদাবিকৃত ভার্টেক্স খুঁজে বের করে ডেটা স্ট্রাকচার থেকে সরাতে হবে।

আমরা রিমুভাল অপারেশন বর্ণনা করার বিকল্প উপায় খুঁজতে পারি, লক্ষ্য করে যে একটি ভার্টেক্স $v$-এর অ্যাডজেসেন্সি লিস্ট ট্রাভার্সের ঠিক পরে, $v$-এর পরে ডেটা স্ট্রাকচারে রাখা সব ভার্টেক্স তার সাবট্রি-তে থাকে। যদি $v$ রুট হয়, $v$-এর পরে ইনসার্ট করা সব অবশিষ্ট ভার্টেক্স সরাতে হবে। তাই রিমুভাল অপারেশন এভাবে বর্ণনা করা যায়:

• যখন আমরা একটি রুট পাই, আমাদের এর পরে ইনসার্ট করা সব অবশিষ্ট ভার্টেক্স খুঁজে বের করে সরাতে হবে।

আমরা এখন দেখতে পাচ্ছি যে এটি একটি স্ট্যাক দিয়ে ইমপ্লিমেন্ট করা যায়:

• যখন আমরা প্রথম একটি ভার্টেক্স ভিজিট করি, আমরা এটি স্ট্যাকে পুশ করি।

• যখন আমরা একটি রুট পাই, আমরা রুট নিজেকে পপ করা পর্যন্ত সব এলিমেন্ট পপ করি।

এটি অবশেষে আমাদের অ্যালগরিদম ইমপ্লিমেন্ট করতে দেয়।

DFS কলের ক্রমের রানটাইম কমপ্লেক্সিটি $O(n + m)$। স্ট্যাক বিবেচনা করলে, এর কমপ্লেক্সিটি $O(n)$-এ অ্যামর্টাইজ হয় কারণ প্রতিটি নোড শুধু একবার পুশ এবং পপ করা হয়। মোট রানটাইম কমপ্লেক্সিটি তাই $O(n + m)$।

অতিরিক্ত মন্তব্য হিসেবে, রুটগুলো বিপরীত টপোলজিক্যাল ক্রমে পাওয়া যায়। অ্যালগরিদমে, একটি ভার্টেক্স রুট যদি তার সাবট্রি-র বাইরে অদাবিকৃত ভার্টেক্সে কোনো এজ না থাকে, অর্থাৎ অন্য সব পৌঁছানো যায় এমন কম্পোনেন্ট হয় তার সাবট্রি-তে (এবং তাই তাদের রুট ইতোমধ্যে পাওয়া হয়েছে) অথবা সাবট্রি-র বাইরে ইতোমধ্যে দাবিকৃত ভার্টেক্সে কানেক্ট করে (যাদের রুটও ইতোমধ্যে পাওয়া হয়েছে)। তাই সব পৌঁছানো যায় এমন কম্পোনেন্ট ইতোমধ্যে পাওয়া হয়েছে, অর্থাৎ তারা কনডেনসেশন গ্রাফের একটি ভ্যালিড বিপরীত টপোলজিক্যাল অর্ডারে প্রবর্তিত হয়।

ইমপ্লিমেন্টেশন#

vector<int> st;    // - stack holding the unclaimed vertices
vector<int> roots; // - keeps track of the SCC roots of the vertices
int timer;         // - dfs timestamp counter
vector<int> t_in;  // - keeps track of the dfs timestamp of the vertices
vector<int> t_low; // - keeps track of the lowest t_in of unclaimed vertices
                   // reachable in the subtree

// implements the tarjan algorithm for strongly connected components
void dfs(int v, vector<vector<int>> const &adj, vector<vector<int>> &components) {

  t_low[v] = t_in[v] = timer++;
  st.push_back(v);

  for (auto u : adj[v]) {
    if (t_in[u] == -1) { // tree-edge
      dfs(u, adj, components);
      t_low[v] = min(t_low[v], t_low[u]);
    } else if (roots[u] == -1) { // back-edge, cross-edge or forward-edge to an unclaimed vertex
      t_low[v] = min(t_low[v], t_in[u]);
    }
  }

  if (t_low[v] == t_in[v]) { // vertex is a root
    components.push_back({v}); // initializes a new component with root v
    while (true) {
      int u = st.back();
      st.pop_back();
      roots[u] = v; // claims the vertex
      if (u == v)
        break;
      components.back().push_back(u); // adds vertex u to the component of v
    }
  }
}

// input: adj -- adjacency list of G
// output: components -- the strongy connected components in G
// output: adj_cond -- adjacency list of G^SCC (by root vertices)
void strongly_connected_components(vector<vector<int>> const &adj,
                                   vector<vector<int>> &components,
                                   vector<vector<int>> &adj_cond) {
  components.clear();
  adj_cond.clear();

  int n = adj.size();

  st.clear();
  roots.assign(n, -1);
  timer = 0;
  t_in.assign(n, -1);
  t_low.assign(n, -1);

  // applies the tarjan algorithm to all the vertices
  // adds vertices to the components in reverse topological order
  for (int v = 0; v < n; v++) {
    if (t_in[v] == -1) {
      dfs(v, adj, components);
    }
  }

  // adds edges to the condensation graph
  adj_cond.assign(n, {});
  for (int v = 0; v < n; v++) {
    for (auto u : adj[v])
      if (roots[v] != roots[u])
        adj_cond[roots[v]].push_back(roots[u]);
  }
}

আমাদের এই কোড Library Checker-এ একটি অ্যাকসেপ্টেড সাবমিশন আছে।

শেষ মন্তব্য হিসেবে, অ্যাডজেসেন্সি লিস্ট ইটারেট করার একটি বিকল্প উপায় আছে। বর্তমানে, আমরা নিম্নলিখিতভাবে করছি:

for (auto u : adj[v]) {
  if (t_in[u] == -1) { // tree-edge
    dfs(u, adj);
    t_low[v] = min(t_low[v], t_low[u]);
  } else if (roots[u] == -1) { // back-edge, cross-edge or forward-edge to an unclaimed vertex
    t_low[v] = min(t_low[v], t_in[u]);
  }
}

বিকল্পভাবে, আমরা এটি করতে পারি:

for (auto u : adj[v]) {
  if (t_in[u] == -1) // vertex is not visited
    dfs(u, adj);
  if (roots[u] == -1) // vertex has not been claimed
    t_low[v] = min(t_low[v], t_low[u]);
}

$t_{low}$ রুটে তথ্য প্রচারের জন্য ব্যবহৃত হয়, এবং যখন আমরা t_low[v] = min(t_low[v], t_in[u]) করি, আমরা জানি যে $u$ এবং $v$ একই এসসিসি-তে থাকে। যদি $t_{low}[u]$ $u$-এর রুট পর্যন্ত প্রচারিত হয়, এটি $v$-এর মাধ্যমেও প্রচারিত হতে পারে কারণ রুট একই। যেহেতু $t_{low}[u] \leq t_{in}[u]$, এটি কোনো বিরোধ তৈরি করে না, বরং $v$-এর রুটের বাউন্ড উন্নত করে।

কনডেনসেশন গ্রাফ তৈরি#

কনডেনসেশন গ্রাফের অ্যাডজেসেন্সি লিস্ট তৈরি করার সময়, আমরা প্রতিটি কম্পোনেন্টের ভার্টেক্স তালিকার প্রথম ভার্টেক্সকে রুট হিসেবে নির্বাচন করি (এটি একটি ইচ্ছামূলক পছন্দ)। এই রুট ভার্টেক্স তার সম্পূর্ণ এসসিসি-কে উপস্থাপন করে। প্রতিটি ভার্টেক্স v-এর জন্য, roots[v] মান সেই রুট ভার্টেক্স নির্দেশ করে যেই এসসিসি-তে v থাকে।

আমাদের কনডেনসেশন গ্রাফ এখন ভার্টেক্স components (একটি স্ট্রংলি কানেক্টেড কম্পোনেন্ট কনডেনসেশন গ্রাফের একটি ভার্টেক্সের সাথে মিলে যায়) এবং অ্যাডজেসেন্সি লিস্ট adj_cond দ্বারা দেওয়া, শুধু স্ট্রংলি কানেক্টেড কম্পোনেন্টগুলোর রুট ভার্টেক্স ব্যবহার করে। লক্ষ্য করুন যে $G$-তে কোনো $a\in C$ থেকে কোনো $b\in C'$-তে প্রতিটি এজের জন্য আমরা $G^\text{SCC}$-তে $C$ থেকে $C'$-তে একটি এজ তৈরি করি (যদি $C\neq C'$)। এর মানে আমাদের ইমপ্লিমেন্টেশনে, কনডেনসেশন গ্রাফে দুটি কম্পোনেন্টের মধ্যে মাল্টিপল এজ থাকতে পারে।

সাহিত্য#

• Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein. Introduction to Algorithms [2005].
• M. Sharir. A strong-connectivity algorithm and its applications in data-flow analysis [1979].
• Robert Tarjan. Depth-first search and linear graph algorithms [1972].

অনুশীলন সমস্যা#

• SPOJ - Good Travels
• SPOJ - Lego
• Codechef - Chef and Round Run
• UVA - 11838 - Come and Go
• UVA 247 - Calling Circles
• UVA 13057 - Prove Them All
• UVA 12645 - Water Supply
• UVA 11770 - Lighting Away
• UVA 12926 - Trouble in Terrorist Town
• UVA 11324 - The Largest Clique
• UVA 11709 - Trust groups
• UVA 12745 - Wishmaster
• SPOJ - True Friends
• SPOJ - Capital City
• Codeforces - Scheme
• SPOJ - Ada and Panels
• CSES - Flight Routes Check
• CSES - Planets and Kingdoms
• CSES - Coin Collector
• Codeforces - Checkposts