Cod sursa(job #408852)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 3 martie 2010 11:51:19
Problema Componente biconexe Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.78 kb
#include <stdio.h>
#include <fstream>
#define size 100010
#define min(a,b) a<b?a:b

using namespace std;

struct nod
{
    int inf;
    nod * next;
}*R[size],*G[size];

int viz[size];
int st[size];
int nr_rez,vf;
int low[size],niv[size];
int nr,n,m,x2,x1;

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",&x1,&x2);
        add(G[x1],x2);
        add(G[x2],x1);
    }
}

void add_rez(int a,int b)
{
    nr_rez++;
    do
    {
        add(R[nr_rez],st[vf]);
        add(R[nr_rez],st[vf-1]);
        vf-=2;
    }while (st[vf+2]!=b || st[vf+1]!=a);
}

void df(int Nod)
{
    viz[Nod]=1;
    low[Nod]=niv[Nod]=nr++;
    for (nod *i=G[Nod];i;i=i->next)
        if (!viz[i->inf])
        {
            st[++vf]=Nod;
            st[++vf]=i->inf;
            df(i->inf);
            if (low[i->inf]>=niv[Nod])
                add_rez(Nod,i->inf);
            low[Nod]=min(low[i->inf],low[Nod]);
        }
        else
            low[Nod]=min(niv[i->inf],low[Nod]);
}

void afish()
{
    printf("%d\n",nr_rez);
    for (int i=1;i<=nr_rez;i++)
    {
        for (nod *j=R[i];j;j=j->next)
            viz[j->inf]=0;
       // memset(viz,0,sizeof(viz));
        for (nod *j=R[i];j;j=j->next)
            if (!viz[j->inf])
            {
                printf("%d ",j->inf);
                viz[j->inf]=1;
            }
        printf("\n");
    }
}


int main ()
{
    freopen ("biconex.in","r",stdin);
    freopen ("biconex.out","w",stdout);
    citire();
    for (int i=1;i<=n;i++)
        if (!viz[i])
        {
            nr=1;
            df(i);
        }
    afish();
    return 0;
}