স্ট্রং ওরিয়েন্টেশন#
একটি আনডিরেক্টেড গ্রাফের স্ট্রং ওরিয়েন্টেশন হলো প্রতিটি এজে এমনভাবে দিক ডিটারমিন করা যেন এটি একটি স্ট্রংলি কানেক্টেড গ্রাফ হয়ে যায়। অর্থাৎ, ওরিয়েন্টেশনের পরে ডিরেক্টেড এজ অনুসরণ করে আমরা যেকোনো ভার্টেক্স থেকে যেকোনো ভার্টেক্সে যেতে পারব।
সমাধান#
অবশ্যই, প্রতিটি গ্রাফে এটি করা সম্ভব নয়। গ্রাফে একটি ব্রিজ কনসিডার করো। আমাদের এতে একটি দিক ডিটারমিন করতে হবে এবং এতে করে এই ব্রিজ শুধুমাত্র একদিকে “পার করা” যাবে। তার মানে আমরা ব্রিজের একপ্রান্ত থেকে অন্যপ্রান্তে যেতে পারি না, তাই আমরা গ্রাফকে স্ট্রংলি কানেক্টেড করতে পারি না।
এখন একটি ব্রিজমুক্ত কানেক্টেড গ্রাফে DFS কনসিডার করো। স্পষ্টতই, আমরা প্রতিটি ভার্টেক্স ভিজিট করব। এবং যেহেতু কোনো ব্রিজ নেই, আমরা যেকোনো DFS ট্রি এজ সরিয়েও এজের নিচ থেকে উপরে যেতে পারি কমপক্ষে একটি ব্যাক এজ ব্যবহার করে। এ থেকে বোঝা যায় যে যেকোনো ভার্টেক্স থেকে DFS ট্রি-র রুটে যাওয়া সম্ভব। এছাড়াও, DFS ট্রি-র রুট থেকে আমরা যেকোনো ভার্টেক্সে যেতে পারি। আমরা একটি স্ট্রং ওরিয়েন্টেশন পেয়েছি!
অন্যভাবে বলতে গেলে, একটি ব্রিজমুক্ত কানেক্টেড গ্রাফকে স্ট্রংলি ওরিয়েন্ট করতে, এতে DFS চালাও এবং DFS ট্রি এজগুলোকে DFS রুট থেকে দূরে এবং অন্য সব এজকে DFS ট্রি-তে ডিসেন্ডেন্ট থেকে অ্যানসেস্টরের দিকে পয়েন্ট করো।
ব্রিজমুক্ত কানেক্টেড গ্রাফগুলোই ঠিক সেই গ্রাফ যাদের স্ট্রং ওরিয়েন্টেশন আছে, এই ফলাফলটিকে রবিন্সের থিওরেম বলা হয়।
সমস্যার সম্প্রসারণ#
চলো এমন একটি গ্রাফ ওরিয়েন্টেশন খুঁজে বের করার সমস্যা কনসিডার করি যেন এসসিসি-র সংখ্যা সর্বনিম্ন হয়।
অবশ্যই, প্রতিটি গ্রাফ কম্পোনেন্ট আলাদাভাবে কনসিডার করা যায়। এখন, যেহেতু শুধুমাত্র ব্রিজমুক্ত গ্রাফই স্ট্রংলি ওরিয়েন্টেবল, তাই চলো সাময়িকভাবে সব ব্রিজ সরিয়ে ফেলি। আমরা কিছু সংখ্যক ব্রিজমুক্ত কম্পোনেন্ট পাব (ঠিক শুরুতে কতগুলো কম্পোনেন্ট ছিল + কতগুলো ব্রিজ ছিল) এবং আমরা জানি যে আমরা তাদের প্রতিটিকে স্ট্রংলি ওরিয়েন্ট করতে পারি।
আমাদের শুধু এজ ওরিয়েন্ট করার অনুমতি ছিল, সরানোর নয়, কিন্তু দেখা যায় যে ব্রিজগুলো যেকোনোভাবে ওরিয়েন্ট করা যায়। অবশ্যই, সবচেয়ে সহজ উপায় হলো প্রতিটি আসল কানেক্টেড কম্পোনেন্টে কোনো পরিবর্তন ছাড়াই উপরে দেখানো অ্যালগরিদম চালানো।
ইমপ্লিমেন্টেশন#
এখানে, ইনপুট হলো n — ভার্টেক্সের সংখ্যা, m — এজের সংখ্যা, তারপর m লাইনে এজের বর্ণনা।
আউটপুট হলো প্রথম লাইনে এসসিসি-র সর্বনিম্ন সংখ্যা এবং দ্বিতীয় লাইনে
m টি ক্যারেক্টারের একটি স্ট্রিং,
হয় > — যার মানে ইনপুটের সংশ্লিষ্ট এজটি বাম থেকে ডান ভার্টেক্সের দিকে
(ইনপুটের মতো) ওরিয়েন্টেড,
অথবা < — উল্টো।
এটি একটি ব্রিজ সার্চ অ্যালগরিদম যা এজ ওরিয়েন্ট করতেও পরিবর্তিত করা হয়েছে, তুমি প্রথম ধাপে এজ ওরিয়েন্ট করে দ্বিতীয় ধাপে ওরিয়েন্টেড গ্রাফে এসসিসি গণনা করতেও পারো।
vector<vector<pair<int, int>>> adj; // adjacency list - vertex and edge pairs
vector<pair<int, int>> edges;
vector<int> tin, low;
int bridge_cnt;
string orient;
vector<bool> edge_used;
void find_bridges(int v) {
static int time = 0;
low[v] = tin[v] = time++;
for (auto p : adj[v]) {
if (edge_used[p.second]) continue;
edge_used[p.second] = true;
orient[p.second] = v == edges[p.second].first ? '>' : '<';
int nv = p.first;
if (tin[nv] == -1) { // if nv is not visited yet
find_bridges(nv);
low[v] = min(low[v], low[nv]);
if (low[nv] > tin[v]) {
// a bridge between v and nv
bridge_cnt++;
}
} else {
low[v] = min(low[v], tin[nv]);
}
}
}
int main() {
int n, m;
scanf("%d %d", &n, &m);
adj.resize(n);
tin.resize(n, -1);
low.resize(n, -1);
orient.resize(m);
edges.resize(m);
edge_used.resize(m);
for (int i = 0; i < m; i++) {
int a, b;
scanf("%d %d", &a, &b);
a--; b--;
adj[a].push_back({b, i});
adj[b].push_back({a, i});
edges[i] = {a, b};
}
int comp_cnt = 0;
for (int v = 0; v < n; v++) {
if (tin[v] == -1) {
comp_cnt++;
find_bridges(v);
}
}
printf("%d\n%s\n", comp_cnt + bridge_cnt, orient.c_str());
}