LightOJ-1026 Critical Links Solutions C++

 

#include<bits/stdc++.h>

#define vi vector<int>

#define pb push_back

using namespace std;

vi g[10005];

int visit[10005],low[10005],in[10005];

vector<pair<int,int> > bridge;

int cnt,timer;

void dfs1(int s,int p)

{

    visit[s]=1;

    low[s]=in[s]=++timer;

    for(int i=0;i<g[s].size();i++)

    {

        if(g[s][i]==p)

            continue;

        else if(visit[g[s][i]])

            low[s]=min(in[g[s][i]],low[s]);

        else

        {

            dfs1(g[s][i],s);

            if(low[g[s][i]]>in[s])

            {

                cnt++;

                if(g[s][i]>s)

                bridge.pb(make_pair(s,g[s][i]));

                else

                bridge.pb(make_pair(g[s][i],s));

            }

            low[s]=min(low[g[s][i]],low[s]);

        }

    }

}

int main()

{

    int t,n,e,u,v,cs=0;

    char a,b,c;

    cin>>t;

    while(t--)

    {

        cnt=0,timer=0;

        cin>>n;

       for(int i=0;i<n;i++)

       {

           g[i].clear();

           visit[i]=0;

       }

       bridge.clear();

       for(int i=0;i<n;i++)

       {

           cin>>u;

            scanf("%c%c%d%c",&c,&c,&e,&c);

           while(e--)

           {

               cin>>v;

               g[u].pb(v);

               g[v].pb(u);

           }

       }

       for(int i=0;i<n;i++)

       {

           if(!visit[i])

           {

               dfs1(i,-1);

           }

       }

      // dfs1(0,-1);

       cout<<"Case "<<++cs<<":"<<endl;

       cout<<cnt<<" critical links"<<endl;

        sort(bridge.begin(), bridge.end());

       for(int i = 0; i <bridge.size(); i++)

       {

         cout << bridge[i].first << " - " << bridge[i].second << endl;

    }

    }

    return 0;

}