मान लीजिए n वर्टेक्स और m एज वाला एक अनभारित, निदेश रहित ग्राफ दिया गया है। ग्राफ में एक ब्रिज एज वह एज है जिसे हटाने से ग्राफ असंबद्ध हो जाता है। हमें दिए गए ग्राफ में ऐसी एज की संख्या ज्ञात करनी है। ग्राफ में समानांतर एज या सेल्फ-लूप नहीं हैं।
उदाहरण के लिए, यदि इनपुट है n = 5, m = 6, edges = {{1, 2}, {1, 3}, {2, 3}, {2, 4}, {2, 5}, {3, 5}}, तो आउटपुट 1 होगा।
ग्राफ में केवल एक ब्रिज एज है जो {2, 4} है।
चरण
इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:
mSize := 100
आकार mSize का सरणी G परिभाषित करें
एक 2D सरणी bridge परिभाषित करें
आकार mSize के सरणी visited, vk, l परिभाषित करें
पूर्णांक युग्मों वाला सरणी edges परिभाषित करें
एक फंक्शन depthSearch() परिभाषित करें जो v, p (डिफ़ॉल्ट -1) लेता है:
visited[v] := 1
vk[v] := l[v] := t++
G[v] में प्रत्येक x के लिए:
यदि x == p, तो जारी रखें
यदि visited[x] सत्य है, तो:
l[v] := min(l[v], vk[x])
अन्यथा:
depthSearch(x, v)
l[v] := min(l[v], l[x])
यदि l[x] > vk[v], तो:
bridge[v][x] := 1
एक फंक्शन bridgeSearch() परिभाषित करें:
t := 0
i := 1 से n तक:
यदि visited[i] असत्य है, तो:
depthSearch(i)
i := 0 से m-1 तक:
a := edges[i] का पहला मान
b := edges[i] का दूसरा मान
b को G[a] के अंत में डालें
a को G[b] के अंत में डालें
bridgeSearch()
ans := 0
i := 1 से n तक:
j := 1 से n तक:
यदि i != j और bridge[i][j], तो:
ans बढ़ाएँ
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