Cod sursa(job #500998)

Utilizator skullLepadat Mihai-Alexandru skull Data 13 noiembrie 2010 23:55:16
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include<stdio.h>
#include<vector>
using namespace std;
#define nmax 100005
#define mmax 200005

int n,m;
struct punct
{
    int x, y;
}st[mmax];
vector<int> G[nmax];
vector<int> sol[nmax];
int lvl[nmax], nr, c[nmax], nrsol, viz[nmax];

void citire()
{
	int i;
	freopen("biconex.in","r",stdin);
    scanf("%d%d",&n,&m);
    int x, y;
    for(i = 1 ;i <= m; ++i)
    {
        scanf("%d%d", &x, &y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
}

void add(int x, int y)
{
    nrsol++;
    do{
        sol[nrsol].push_back(st[nr].y);
        nr--;
    }while(st[nr+1].x!=x || st[nr+1].y!=y);
    sol[nrsol].push_back(st[nr+1].x);
}

void dfs(int nod,int tata)
{
	int i, x;
    lvl[nod] = lvl[tata] + 1;
    c[nod] = lvl[nod];
    viz[nod] = 1;
    for( i = 0; i < G[nod].size(); ++i)
    {
        x = G[nod][i];
        if( !viz[x] )
        {
            st[++nr].x=nod;
            st[nr].y=x;
            dfs(x, nod);
            if(c[x]<c[nod])
                c[nod]=c[x];
            if(c[x] >= lvl[nod])
                add(nod,x);
        }
        else if(tata!=x && c[x]<c[nod])
            c[nod]=c[x];
    }
}

void afisare()
{
	int i, j;
	freopen("biconex.out","w",stdout);
    printf("%d\n",nrsol);
    for(i = 1; i <= nrsol;++i)
    {
        for(j = 0; j < sol[i].size(); ++j)
            printf("%d ",sol[i][j]);
        printf("\n");
    }
}

int main()
{
    citire();
    dfs(1,0);
    afisare();
    return 0;
}