Cod sursa(job #434174)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 5 aprilie 2010 11:32:30
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.63 kb
#include <stdio.h>
#include <algorithm>
#define IN "biconex.in"
#define OUT "biconex.out"
#define L 100005

using namespace std;

struct nod
{
    int inf;
    nod *next;
}*V[L],*R[L];

int num, n, m, sf, a, b, nr;
int niv[L];
int viz[L];
int low[L];
int st[L*2];

void add(nod *&A,int i)
{
    nod *q=new nod;
    q->inf=i;
    q->next=A;
    A=q;
}

void citire()
{
    scanf ("%d %d", &n, &m);
    for (int i=0;i<m;i++)
    {
        scanf ("%d %d", &a, &b);
        add(V[a],b);
        add(V[b],a);
    }
}

void ad(int a,int b)
{
    do
    {
        add(R[num], st[--sf]);
        add(R[num], st[--sf]);
    }while (st[sf]!=a || st[sf+1]!=b);
    num++;
}

void df(int P)
{
    viz[P]=1;
    low[P]=niv[P]=nr++;
    for (nod *i=V[P];i;i=i->next)
        if (!viz[i->inf])
        {
            st[sf++]=i->inf;
            st[sf++]=P;
            df(i->inf);
            if (low[i->inf]>=niv[P])
                ad(i->inf, P);
            low[P]= min(low[P],low[i->inf]);
        }
        else
            low[P]=min(low[P], niv[i->inf]);
}

void solve()
{
    for (int i=1;i<=n;i++)
        if (!viz[i])
            df(i);

    printf("%d\n",num);
    for (int i=0;i<num;i++)
    {
        for (nod *j=R[i];j;j=j->next)
            viz[j->inf]=0;

        for (nod *j=R[i];j;j=j->next)
            if (!viz[j->inf])
            {
                viz[j->inf]=1;
                printf("%d ", j->inf);
            }
        printf("\n");
    }
}

int main()
{
    freopen (IN ,"r", stdin);
    freopen (OUT , "w", stdout);
    citire();
    solve();
    return 0;
}