Cod sursa(job #901098)

Utilizator RaduDoStochitoiu Radu RaduDo Data 1 martie 2013 00:17:28
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<list>
#include<bitset>
#define INF 0x3f3f3f3f
#define mp make_pair
#define pb push_back
#define pf push_front
#define maxn 100010
using namespace std;
list < pair < int, int > > stiva;
vector < int > G[maxn],sol[maxn];
int d[maxn],low[maxn],n,m,x,y,i,j,c;

void empty(int x, int y)
{
    while(stiva.front().first!=x && stiva.front().second!=y)
    {
        sol[c].pb(stiva.front().second);
        stiva.pop_front();
    }
    sol[c].pb(x);
    sol[c].pb(y);
    stiva.pop_front();
}

void DFS(int x, int t)
{
    int y,i;
    d[x] = d[t] + 1;
    low[x] = d[x];
    for(i=0; i<G[x].size(); ++i)
    {
        y=G[x][i];
        if(y!=t)
        {
            if(!d[y])
            {
                stiva.pf(mp(x,y));
                DFS(y,x);
                if(low[y]>=d[x]) { c++; empty(x,y); }
            }
            if( low[x] > low[y] ) low[x] = low[y];
        }
    }
}

int main()
{
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    scanf("%d%d",&n,&m);
    while(m--)
        scanf("%d%d",&x,&y),G[x].pb(y),G[y].pb(x);
    stiva.pb(mp(1,0));
    DFS(1,0);
    printf("%d\n",c);
    for(i=1; i<=c; ++i)
    {
        for(j=0; j<sol[i].size(); ++j)
            printf("%d ",sol[i][j]);
        printf("\n");
    }
    return 0;
}