Cod sursa(job #407650)

Utilizator hasegandaniHasegan Daniel hasegandani Data 2 martie 2010 15:32:19
Problema Componente biconexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include<stdio.h>
#include<vector>

using namespace std;

#define Nmax 100010

vector <int> l[Nmax];
int N,v[Nmax],t[Nmax],niv[Nmax];
int comp[Nmax],K;
int grup[Nmax],c[Nmax],m;

void componenta(int k,int l)
{
    grup[++K]=m+1;
    for(; k!=l ; k=t[k])
        {
        comp[k]=1;
        c[++m]=k;
        }
    c[++m]=l;
}

void DF(int k)
{
    v[k]=1;
    int val=k;
    for(int i=0;i<(int)l[k].size();++i)
        if (!v[ l[k][i] ])
            {
            t[ l[k][i] ]=k;
            niv[ l[k][i] ]= niv[k]+1;
            DF( l[k][i] );
            }
        else
        if (niv[ l[k][i] ] < niv[ val ])
            val = l[k][i];
    if (comp[k])
        return ;

    if (niv[k]>1)
        componenta(k,val);
}

void solve()
{
    for(int i=1;i<=N;++i)
        if (!v[i])
            {
            niv[i]=1;
            DF(i);
            }

    printf("%d\n",K);
    grup[++K]=m+1;
    for(int i=1;i<K;++i)
        {
        for(int j=grup[i];j<grup[i+1];++j)
            printf("%d ",c[j]);
        printf("\n");
        }
}

void cit();

int main()
{
    cit();
    solve();
    return 0;
}

void cit()
{
    int a,b,M;
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    scanf("%d%d",&N,&M);
    for(int i=1;i<=M;++i)
        {
        scanf("%d%d",&a,&b);
        l[a].push_back(b);
        l[b].push_back(a);
        }
}