Articulation and Bridges, C++ (gcc)

Articulation and Bridges

/*
// Sample code to perform I/O:

cin >> name;                            // Reading input from STDIN
cout << "Hi, " << name << ".\n";        // Writing output to STDOUT

// Warning: Printing unwanted or ill-formatted data to output will cause the test cases to fail
*/

// Write your code here
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
vector<int>ar;
vector<pair<int,int>>br;
vector<vector<int>>gr(11);
int dis[11];
int low[11];
int pr[11];
int v[11];
int t=1;
void dfar(int s)
{
    v[s]=1;
    dis[s]=t;
    low[s]=t;
    t++;
    int c=0;
    for(int i=0;i<gr[s].size();++i)
    {
        int d=gr[s][i];
        if(v[d]==-1)
        {
            c++;
            pr[d]=s;
            dfar(d);
            low[s]=min(low[s],low[d]);
            if(pr[s]==-1 && c==2)
                ar.pb(s);
            else if(pr[s]!=-1 && dis[s]<=low[d])
                ar.pb(s);
        }
        else if(d!=pr[s])
            low[s]=min(low[s],dis[d]);
    }
}
void dfbr(int s)
{
    v[s]=1;
    dis[s]=t;
    low[s]=t;
    t++;
    int c=0;
    for(int i=0;i<gr[s].size();++i)
    {
        int d=gr[s][i];
        if(v[d]==-1)
        {
            c++;
            pr[d]=s;
            dfbr(d);
            low[s]=min(low[s],low[d]);
            if(dis[s]<low[d])
            {
                int a[2];
                a[0]=s;
                a[1]=d;
                sort(a,a+2);
                br.pb(mp(a[0],a[1]));
            }
        }
        else if(d!=pr[s])
            low[s]=min(low[s],dis[d]);
    }
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;++i)
    {
        int u,v;
        cin>>u>>v;
        gr[u].pb(v);
        gr[v].pb(u);
    }
    t=1;
    for(int i=0;i<11;++i)
        dis[i]=low[i]=pr[i]=v[i]=-1;
    dfar(0);
    t=1;
    for(int i=0;i<11;++i)
        dis[i]=low[i]=pr[i]=v[i]=-1;
    dfbr(0);
    sort(ar.begin(),ar.end());
    sort(br.begin(),br.end());
    cout<<ar.size()<<endl;
    for(int i=0;i<ar.size();++i)
        cout<<ar[i]<<" ";
    cout<<endl;
    cout<<br.size()<<endl;
    for(int i=0;i<br.size();++i)
        cout<<br[i].first<<" "<<br[i].second<<endl;
}


run \| edit \| history \| help	0