C++ में नेटवर्क में क्रिटिकल कनेक्शन्स

मान लीजिए कि n सर्वर हैं। और ये 0 से n-1 तक एक नेटवर्क बनाने वाले अप्रत्यक्ष सर्वर-से-सर्वर कनेक्शन से जुड़े होते हैं जहां कनेक्शन [i] =[ए, बी] सर्वर ए और बी के बीच एक कनेक्शन का प्रतिनिधित्व करता है। सभी सर्वर सीधे या किसी अन्य सर्वर के माध्यम से जुड़े हुए हैं। अब, एक महत्वपूर्ण कनेक्शन एक कनेक्शन है, अगर इसे हटा दिया जाता है, तो यह कुछ सर्वर को किसी अन्य सर्वर तक पहुंचने में असमर्थ बना देगा। हमें सभी महत्वपूर्ण कनेक्शन खोजने होंगे।

इसलिए, यदि इनपुट n =4 जैसा है और कनेक्शन =[[0,1], [1,2], [2,0], [1,3]],

तो आउटपुट [[1,3]]

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक सेट परिभाषित करें

• सरणी डिस्क परिभाषित करें

• एक सरणी कम परिभाषित करें

• एक 2डी सरणी रेट परिभाषित करें

• फ़ंक्शन dfs() को परिभाषित करें, यह नोड, बराबर, एक 2D सरणी ग्राफ़,

  . लेगा

• यदि नोड का दौरा किया गया है, तो -

  • वापसी

• देखे गए में नोड डालें

• डिस्क [नोड] :=समय

• कम [नोड] :=समय

• (समय 1 से बढ़ाएँ)

• ग्राफ में सभी तत्वों x के लिए[नोड]

  • यदि x बराबर के समान है, तो -

    • निम्नलिखित भाग पर ध्यान न दें, अगले पुनरावृत्ति पर जाएं

  • यदि x विज़िट नहीं किया गया है, तो -

    • dfs(x, नोड, ग्राफ)

    • कम [नोड] :=कम से कम [नोड] और कम [x]

    • अगर डिस्क [नोड] <निम्न[x], तो -

      • रिट के अंत में {नोड, x} डालें

  • अन्यथा

    • कम [नोड] :=कम से कम [नोड] और डिस्क [x]

• मुख्य विधि से, निम्न कार्य करें -

  • डिस्क का आकार n + 1 के रूप में सेट करें

  • कम का आकार n + 1 के रूप में सेट करें

  • समय:=0

  • आकार ग्राफ़ n + 1 की सूचियों की एक सरणी परिभाषित करें

  • इनिशियलाइज़ i:=0 के लिए, जब i

    • यू:=वी[i, 0]

    • डब्ल्यू:=वी[i, 1]

    • ग्राफ़ के अंत में w डालें[u]

    • ग्राफ़ के अंत में आपको डालें[w]

  • dfs(0, -1, ग्राफ़)

  • वापसी रिट

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto> > v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << "[";
      for(int j = 0; j <v[i].size(); j++){
         cout << v[i][j] << ", ";
      }
      cout << "],";
   }
   cout << "]"<<endl;
}
class Solution {
   public:
   set<int> visited;
   vector<int> disc;
   vector<int> low;
   int time;
   vector<vector<int> > ret;
   void dfs(int node, int par, vector<int> graph[]) {
      if (visited.count(node))
      return;
      visited.insert(node);
      disc[node] = low[node] = time;
      time++;
      for (int x : graph[node]) {
         if (x == par)
         continue;
         if (!visited.count(x)) {
            dfs(x, node, graph);
            low[node] = min(low[node], low[x]);
            if (disc[node] < low[x]) {
               ret.push_back({ node, x });
            }
         } else{
            low[node] = min(low[node], disc[x]);
         }
      }
   }
   vector<vector<int> > criticalConnections(int n, vector<vector<int> >& v) {
      disc.resize(n + 1);
      low.resize(n + 1);
      time = 0;
      vector<int> graph[n + 1];
      for (int i = 0; i < v.size(); i++) {
         int u = v[i][0];
         int w = v[i][1];
         graph[u].push_back(w);
         graph[w].push_back(u);
      }
      dfs(0, -1, graph);
      return ret;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{0,1},{1,2},{2,0},{1,3}};
   print_vector(ob.criticalConnections(4,v));
}

इनपुट

4, {{0,1},{1,2},{2,0},{1,3}}

आउटपुट

[[1, 3, ],]