মান লিজিয়ে, একটি অ-भারসাম্য, অনির্দেশ গ্রাফ দেওয়া আছে যাতে n টি ভেরটেক্স এবং m টি এজ রয়েছে। গ্রাফে একটি ব্রিজ এজ হলো এমন একটি এজ যেটি মুছে ফেললে গ্রাফটি ডিসকনেক্টেড হয়ে যায়। আমাদের লক্ষ্য হলো দেওয়া গ্রাফে এতরকম ব্রিজ এজের সংখ্যা বের করা। গ্রাফে প্যারালেল এজ বা সেলফ-লুপ নেই।
যেমন, ইনপুট হলে n = 5, m = 6, edges = {{1, 2}, {1, 3}, {2, 3}, {2, 4}, {2, 5}, {3, 5}}, তবে আউটপুট হবে 1।
গ্রাফে মাত্র একটি ব্রিজ এজ রয়েছে যা হলো {2, 4}।
সমাধানের ধাপসমূহ
এই সমস্যাটি সমাধান করার জন্য নিচের ধাপগুলো অনুসরণ করব:
mSize := 100 G অ্যারে সংজ্ঞায়িত করুন আকার mSize bridge ২D অ্যারে সংজ্ঞায়িত করুন visited অ্যারে সংজ্ঞিত করুন আকার mSize vk এবং l অ্যারে সংজ্ঞায়িত করুন আকার mSize edges অ্যারে সংজ্ঞায়িত করুন যাতে ইন্টিজার পেয়ার থাকে depthSearch() ফাংশন সংজ্ঞায়িত করুন, যা v, p (ডিফল্ট -1) গ্রহণ করবে: visited[v] := 1 vk[v] := (l[v] = t কে ১ বাড়িয়ে) G[v]-র প্রতিটি x জন্য: if x == p, তবে: continue if visited[x] নন-জিরো, তবে: l[v] := min(l[v], vk[x]) অন্যথায়: depthSearch(x, v) l[v] := min(l[v], l[x]) if l[x] > vk[v], তবে: bridge[v, x] := 1 bridgeSearch() ফাংশন সংজ্ঞায়িত করুন: t := 0 i := 1 থেকে n পর্যন্ত: if not visited[i] নন-জিরো, তবে: depthSearch(i) i := 0 থেকে m-1 পর্যন্ত: a := edges[i]-র ১ম মান b := edges[i]-র ২য় মান G[a]-র শেষে b যোগ করুন G[b]-র শেষে a যোগ করুন bridgeSearch() ans := 0 i := 1 থেকে n পর্যন্ত: j := 1 থেকে n পর্যন্ত: if i != j এবং bridge[i, j], তবে: ans ১ বাড়িয়ে return ans
উদাহরণ
নিচের ইমপ্লিমেন্টেশনটি দেখুন আরও ভালো বুঝতে:
#include <bits/stdc++.h> using namespace std; const int mSize = 100; vector <int> G[mSize]; int n, m, t; vector<vector<int>> bridge(mSize, vector<int>(mSize)); vector <int> visited(mSize); vector <int> vk(mSize, -1), l(mSize, -1); vector<pair<int, int>> edges; void depthSearch(int v, int p = -1) { visited[v] = 1; vk[v] = l[v] = t++; for (auto x: G[v]) { if (x == p) { continue; } if (visited[x]) { l[v] = min(l[v], vk[x]); } else { depthSearch(x, v); l[v] = min(l[v], l[x]); if (l[x] > vk[v]) { bridge[v][x] = 1; } } } } void bridgeSearch() { t = 0; for (int i = 1; i <= n; ++i) { if (!visited[i]) { depthSearch(i); } } } int solve(){ for (int i = 0; i < m; ++i) { int a, b; a = edges[i].first; b = edges[i].second; G[a].push_back(b); G[b].push_back(a); } bridgeSearch(); int ans = 0; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { if (i != j and bridge[i][j]) ans++; } } return ans; } int main() { n = 5, m = 6; edges = {{1, 2}, {1, 3}, {2, 3}, {2, 4}, {2, 5}, {3, 5}}; cout<< solve(); return 0; } ইনপুট
5, 6, {{1, 2}, {1, 3}, {2, 3}, {2, 4}, {2, 5}, {3, 5}} আউটপুট
1
