Solution UVA: 796 - Critical Links

 

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss796 - Critical Links	Accepted	C++11	0.020	0.000	3287	1 mins ago

Suggest:

- To solve you need to know Finding Bridge in Graph (because this is a classic algogrithm of graph)

- This is link that help me understand this algorithm very easy

Important:

- Num[u]: index dfs to u

- Low[u] : index dfs to u (but smallest) 

Example:

- You dfs 1 -> 2 -> 3->4 but can 2->4  (this num[4] is 4, but low[4] is 3) 

Fomular: 

- If (num[v] == low[v]) => (u,v) is bridge

#include<bits/stdc++.h>

#define int long long

#define oo LLONG_MAX

#define pb push_back

#define FOR(i, a, b) for(int i=a; i<=b; i++)

using namespace std;

const int N= 1000111;

int t, n, u, v;

char c;

vector<int> a[N];

set<pair<int, int>> bridge;

int num[N], low[N];

int timeDfs = 0; // Thứ tự duyệt DFS

void dfs(int u, int pre) {

    num[u] = low[u] = ++timeDfs;

    for (int v : a[u]){

        if (v == pre) continue;

        if (!num[v]) {

           

            dfs(v, u);

           

            low[u] = min(low[u], low[v]);

            if (low[v]==num[v]) bridge.insert({min(u,v), max(u,v)});

        }

        else low[u] = min(low[u], num[v]);

    }

}

void reset(){

    FOR(i, 0, t-1) a[i].clear(), num[i]= 0, low[i]= 0;

    bridge.clear();

    timeDfs = 0;

}

void read(){

   

    cin >> u >> c >> n >> c;

       

    FOR(i, 1, n){

       

        cin >> v;

        a[u].pb(v);

        a[v].pb(u);

    }

}

int32_t main(){

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    while(cin >> t){    

       

        reset();

        FOR(i, 1, t) read();

       

        for (int i = 0; i <= t-1; i++)

            if (!num[i]) dfs(i, i);

       

        cout << bridge.size() << " critical links" << endl;

        for(auto x:bridge) cout<<x.first<<" - "<<x.second<<"\n";    

        cout<<"\n";

    }

}