समस्या विवरण
n सर्वर हैं जो 0 से n-1 तक संख्यांकित हैं। connections[i] = [a,b] सर्वर a और b के बीच अनिर्देशित कनेक्शन दर्शाता है। सभी सर्वर प्रत्यक्ष या अप्रत्यक्ष रूप से जुड़े हैं। एक क्रिटिकल कनेक्शन वह किनारा है जिसे हटाने पर कुछ सर्वर अन्य सर्वरों तक नहीं पहुंच पाएंगे (यानी ग्राफ असंबद्ध हो जाएगा)। सभी क्रिटिकल कनेक्शन ढूंढने हैं।
उदाहरण
इनपुट
n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
आउटपुट
[[1,3]]
समाधान दृष्टिकोण (टार्जन एल्गोरिदम - ब्रिज खोज)
DFS का उपयोग करके ब्रिज (bridges) ढूंढें। प्रत्येक नोड के लिए:
disc[u]: खोज समय (discovery time)low[u]: u से पहुंचने योग्य सबसे पहला पूर्वज
किनारा (u,v) ब्रिज है यदि disc[u] < low[v] (v का सबट्री u या उसके पूर्वजों तक बैक एज के बिना नहीं पहुंच सकता)।
कार्यकारी प्रोग्राम
#include <bits/stdc++.h>
using namespace std;
void printVec(vector<vector<int>> v) {
cout << "[";
for (auto& e : v) {
cout << "[" << e[0] << "," << e[1] << "],";
}
cout << "]" << endl;
}
class Solution {
public:
unordered_set visited;
vector disc, low;
int timer = 0;
vector> bridges;
void dfs(int u, int parent, vector adj[]) {
visited.insert(u);
disc[u] = low[u] = timer++;
for (int v : adj[u]) {
if (v == parent) continue;
if (!visited.count(v)) {
dfs(v, u, adj);
low[u] = min(low[u], low[v]);
if (disc[u] < low[v]) {
bridges.push_back({u, v});
}
} else {
low[u] = min(low[u], disc[v]);
}
}
}
vector> criticalConnections(int n, vector>& edges) {
disc.assign(n, 0);
low.assign(n, 0);
timer = 0;
bridges.clear();
visited.clear();
vector adj[n];
for (auto& e : edges) {
adj[e[0]].push_back(e[1]);
adj[e[1]].push_back(e[0]);
}
dfs(0, -1, adj);
return bridges;
}
};
int main() {
Solution ob;
vector> edges = {{0,1},{1,2},{2,0},{1,3}};
printVec(ob.criticalConnections(4, edges));
return 0;
}
आउटपुट
[[1,3],]