Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में नेटवर्क में क्रिटिकल कनेक्शन (Critical Connections in a Network)


समस्या विवरण

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],]
  1. C++ में प्रोसेस मारें C++ में प्रोसेस मारें

    मान लीजिए हमारे पास n प्रोसेस हैं, यहां प्रत्येक प्रोसेस की एक अद्वितीय आईडी होती है जिसे PID या प्रोसेस आईडी कहा जाता है और इसका PPID (पैरेंट प्रोसेस आईडी) भी होता है। प्रत्येक प्रोसेस का केवल एक पैरेंट प्रोसेस होता है, लेकिन उसके एक या अधिक चाइल्ड प्रोसेस हो सकते हैं। यह एक ट्री संरचना की तरह है।

  1. C++ में गिलहरी सिमुलेशन C++ में गिलहरी सिमुलेशन

    एक पेड़, एक गिलहरी, और कई नट्स हैं। स्थितियों को 2D ग्रिड में सेल द्वारा दर्शाया जाता है। आपका लक्ष्य गिलहरी के लिए सभी नट्स को इकट्ठा करके उन्हें एक-एक करके पेड़ के नीचे रखने के लिए न्यूनतम दूरी ढूंढना है। गिलहरी एक समय में अधिकतम एक नट ले जा सकती है और चार दिशाओं में आगे बढ़ सकती है - ऊपर, नीचे,

  1. C++ में फ्लो नेटवर्क में न्यूनतम s-t कट ढूंढना C++ में फ्लो नेटवर्क में न्यूनतम s-t कट ढूंढना

    मान लीजिए हमारे पास निम्नलिखित फ्लो नेटवर्क है। जैसा कि हम जानते हैं एक s-t कट एक ऐसा कट है जिसमें स्रोत s नोड और सिंक t नोड को अलग-अलग उपसमुच्चय में होना आवश्यक है, और इसमें स्रोत सेट से सिंक साइड की ओर जाने वाले किनारे शामिल हैं। यहां s-t कट की क्षमता कट-सेट में प्रत्येक किनारे की क्षमता के योग द