Cod sursa(job #994364)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 5 septembrie 2013 13:33:02
Problema Componente biconexe Scor 34
Compilator cpp Status done
Runda Arhiva educationala Marime 2.02 kb
#include <algorithm>
#include <stack>
#include <cstdio>
#include <vector>
#include <bitset>
#include <cstring>

#define FOR(i,a,b) for( int i = (a) ; i <= (b); ++i)
#define Nmax 100005
#define Mmax 200005
#define pb push_back

using namespace std;

vector< int > lv[Nmax],sol[Nmax];
bitset< Nmax > used;
stack<pair<int,int> > s;
int niv[ Nmax ],tata[ Nmax ],artic[ Nmax ], nmin[ Nmax ];

int N,M,fr,x,y,i,ncc=0;

void get_graph()
{
    scanf("%d %d",&N,&M);
    int a,b;
    FOR(i,1,M){
        scanf("%d %d",&a,&b);
        lv[ a ].push_back(b);
        lv[ b ].push_back(a);
    }
}

void DFS ( int nodc ){
    used[ nodc ] = true;
    nmin[ nodc ] = niv[ nodc ];
    for(vector<int> ::iterator it = lv[ nodc ].begin(); it != lv[ nodc ].end(); ++it)
        if(used[*it] == false){
            s.push(make_pair(nodc,*it));
            niv[ *it ] = niv[ nodc ]+1;
            if(nodc == 1) ++fr;
            tata[ *it ] = nodc;
            DFS(*it);
            if(nmin[ *it ] < nmin[ nodc ])
                nmin[ nodc ]=nmin[ *it ];
            if(nmin[ *it ] >= niv[ nodc ])
            {
                artic[ nodc ] = 1;
                ++ncc;
                x=s.top().first;
                y=s.top().second;
                s.pop();
                sol[ncc].pb(x);sol[ncc].pb(y);
                while(x!=nodc || y!=*it)
                {
                    x=s.top().first;
                    y=s.top().second;
                    s.pop();
                    sol[ncc].pb(x);
                }
            }
        }
        else if(tata[ nodc ] != *it && nmin[ *it ] < niv [ nodc ])
                    nmin[ nodc ]= niv [ *it ];
}

int j;
int main()
{
    freopen("biconex.in", "r", stdin);
    freopen("biconex.out", "w", stdout);
    get_graph();
    niv[ 1 ]=1;
    DFS(1);
    if(fr<=1)artic[1]=0;
    printf("%d\n",ncc);
    for(i=1;i<=ncc;i++)
    {
        for(j=0;j<sol[i].size();j++)
            printf("%d ",sol[i][j]);
        printf("\n");
    }
    return 0;
}