การเชื่อมต่อสำคัญในเครือข่ายใน C++

มี n เซิร์ฟเวอร์ หมายเลข 0 ถึง n-1 เชื่อมต่อแบบไม่มีทิศทาง connections[i] = [a,b] ทุกเซิร์ฟเวอร์เชื่อมต่อโดยตรงหรือผ่านอื่นๆ การเชื่อมต่อสำคัญ (Critical Connection) คือการเชื่อมต่อที่ถ้าลบออกจะทำให้บางเซิร์ฟเวอร์เข้าถึงอีกตัวไม่ได้ ต้องหาการเชื่อมต่อสำคัญทั้งหมด

เช่น n=4, connections=[[0,1],[1,2],[2,0],[1,3]] เอาต์พุต=[[1,3]]

วิธีแก้ − ใช้ Tarjan's Algorithm หา Bridge ในกราฟ (DFS + Discovery Time + Low Link)

ตัวอย่าง

#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, 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++; 
        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++){ graph[v[i][0]].push_back(v[i][1]); graph[v[i][1]].push_back(v[i][0]); } 
        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, ],]