C++-এ নেটওয়ার্কে ক্রিটিক্যাল কানেকশন (Critical Connections in a Network) বের করা

n সংখ্যক সার্ভার ০ থেকে n-1 পর্যন্ত নম্বর দেওয়া আছে। এগুলো অনির্দেশিত কানেকশন দিয়ে সংযুক্ত। একটি ক্রিটিক্যাল কানেকশন হলো এমন একটি কানেকশন যেটি সরালে কিছু সার্ভার অন্য সার্ভারএ পৌঁছাতে পারবে না। সব ক্রিটিক্যাল কানেকশন বের করতে হবে।

উদাহরণ

ইনপুট: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]

আউটপুট: [[1,3]]

সমাধানের ধাপসমূহ (Tarjan's Algorithm)

1. DFS ব্যবহার করে প্রতিটি নোডের ডিসকভারি টাইম (disc) এবং লো ভ্যালু (low) ক্যালকুলেট করুন।
2. low[v] > disc[u] হলে u-v একটি ব্রিজ (ক্রিটিক্যাল কানেকশন)।
3. সময় কমপ্লেক্সিটি: O(V + E)।

প্রোগ্রাম উদাহরণ

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<vector<int>> 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, low;
    int time = 0;
    vector<vector<int>> bridges;
    
    void dfs(int u, int parent, vector<int> adj[]) {
        visited.insert(u);
        disc[u] = low[u] = time++;
        
        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<vector<int>> criticalConnections(int n, vector<vector<int>>& edges) {
        disc.resize(n);
        low.resize(n);
        vector<int> 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<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]]