1026 - Critical Links (LightOJ)

#include<bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef pair<int,int> pii;
typedef vector< pii > vii;

#define ll          long long
#define ff          first
#define ss          second
#define pb          push_back
#define mkp         make_pair
#define sz          size()

#define forf(a,b,c)    for(int i=a;i<=b;i+=c)
#define forr(a,b,c)    for(int i=a;i>=b;i-=c)
#define all(a)      a.begin(),a.end()
#define mem(a,b)    memset(a,b,sizeof(a))
#define pi          2*acos(0.0)
#define End         return 0;

vector<int>adj[10007];
//bool visit[100007];
int low[10007],AP[10007],discovery[10007];
int Time=0;
vector< pair<int,int> >res;

bool sortbysec(const pair<int,int> &a,
              const pair<int,int> &b)
{
    if(a.ff==b.ff) return a.ss<b.ss;
    return (a.ff < b.ff);
}


void dfsAP(int src, int parent){
    low[src]=discovery[src]= (++Time);

    int children=0;
    for(int i=0;i<adj[src].size();i++){
        int w=adj[src][i];

        if(w!=parent){
            if(discovery[w]==0){
                children++;
                dfsAP(w,src);

                if(discovery[src]<low[w]) res.push_back(make_pair(src,w)); //Condition 1
                low[src]=min(low[src],low[w]);
            }

            else{
                low[src]=min(low[src],discovery[w]);
            }
        }
    }
    return;
}


int main()
{
    int t; cin>>t;
    for(int o=1;o<=t;o++){

            memset(low,0,sizeof(low));
            memset(discovery,0,sizeof(discovery));
    Time=0;
    int n;
    cin>>n;

    for(int i=0;i<n;i++) {
        int u,k; char ch;
        scanf("%d %c%d%c",&u,&ch,&k,&ch);
        for(int I=0;I<k;I++){
            int kk; cin>>kk;
            if(u<kk){
            adj[u].push_back(kk);
            adj[kk].push_back(u);
            }
        }
    }


    cout<<"Case "<<o<<":"<<endl;
    cout<<res.sz<<" critical links"<<endl;


    for(int i=0;i<res.sz;i++){
        if(res[i].ff>res[i].ss) swap(res[i].ff,res[i].ss);
    }

    sort(all(res),sortbysec);

    for(int i=0;i<res.sz;i++){
        cout<<res[i].ff<<" - "<<res[i].ss<<endl;
    }
    for(int i=0;i<10007;i++) {
        adj[i].clear();
    }
    res.clear();
}
return 0;
}