BridgeEdge, C++ (gcc)

BridgeEdge

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
const int N=1e6;
vector<ll> v[N],tin(N),low(N);
vector<pair<ll,ll> > ans;
set<pair<ll,ll> > S;
ll vis[N+1],timer=0;

void dfs(ll s,ll p)
{
    vis[s]=1;
    tin[s]=timer;
    low[s]=timer;
    timer++;
    
    for(auto des : v[s])
    {
        if(des==p)       continue;
        if(vis[des])     {if(S.find({des,s})==S.end())  cout<<s<<" "<<des<<endl; low[s]=min(low[s],tin[des]),S.insert({s,des});}
        else
        {
            if(S.find({des,s})==S.end())  cout<<s<<" "<<des<<endl;
             dfs(des,s);
             low[s]=min(low[s],low[des]);
            if(low[des]>tin[s]) cout<<des<<" "<<s<<endl;
            S.insert({s,des});S.insert({des,s});
        }
    }
}

int main()
{
    ll n,m,t=1;
    while(cin>>n>>m)
    {
        if(n==0 && m==0) break;
        for(int i=0;i<N;i++)   v[i].clear();
        S.clear();
        for(int i=0;i<m;i++)
        {
            ll x,y;
            cin>>x>>y;
            v[x].push_back(y);
            v[y].push_back(x);
        }
        
        ll timer=0;
        memset(vis,0,sizeof(vis));
        
        cout<<t++<<endl;
        cout<<endl;
        for(int i=0;i<n;i++)
        {
            if(!vis[i])
                timer=0,dfs(i,-1);
        }
        cout<<"#"<<endl;
    }
}


run \| edit \| history \| help	0