Cod sursa(job #260300)

Utilizator mircea_infoSuciu Mircea-Gabriel mircea_info Data 16 februarie 2009 21:34:50
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.97 kb
#include <cstdio>
#define max1 200001
#define max2 100001

struct nod{ int inf;nod *urm;};
typedef nod *graf;
graf g[100001], sol[200001];

int n,m,nrsol,nr;
int st[200001],vf;
int sir[100001],s1[100001],s2[100001],prt[100001];

int minim(int x, int y)
{
    return x<y?x:y;
}

void baga(int x, int y)
{
	nod *q;
	q=new nod;
	q->inf=x;
	q->urm=g[y];
	g[y]=q;
	q=new nod;
	q->inf=y;
	q->urm=g[x];
	g[x]=q;
}

void update(int xx,int yy)
{
    nod *q1;
	int z1,z2;
	nrsol++;
	do
	{
	    z1=st[vf-1];
	    z2=st[vf];
        q1=new nod;
        q1->inf=z1;
        q1->urm=sol[nrsol];
        sol[nrsol]=q1;
        q1=new nod;
        q1->inf=z2;
        q1->urm=sol[nrsol];
        sol[nrsol]=q1;
        vf-=2;
	}  while((z1-xx)||(z2-yy));
}

void dfs(int x)
{
    nod *q;
    sir[x]=1;
    s1[x]=s2[x]=nr++;
    for(q=g[x];q;q=q->urm)
    {
        if(!sir[q->inf])
        {
            st[++vf]=x;
            st[++vf]=q->inf;
            prt[q->inf]=x;
            dfs(q->inf);
            if(s2[q->inf]>=s1[x])
                update(x,q->inf);
            s2[x]=minim(s2[x],s2[q->inf]);
        }
        if(q->inf-prt[x])
            s2[x]=minim(s2[x],s1[q->inf]);
     }
}

void solve()
{
	for(int i=1;i<=n;i++)
        if(!sir[i])
        {
            nr=1;
            dfs(i);
        }
}

void afisare()
{
    nod *q1;
	printf("%d\n",nrsol);
	for(int i=1;i<=nrsol;i++)
	{
	    for(q1=sol[i];q1;q1=q1->urm)
            sir[q1->inf]=0;
        for(q1=sol[i];q1;q1=q1->urm)
        {
            if(!sir[q1->inf])
            {
                sir[q1->inf]=1;
                printf("%d ",q1->inf);
            }
        }
        printf("\n");
	}
}

int main()
{
	freopen("biconex.in","rt",stdin);
	freopen("biconex.out","wt",stdout);
	int x,y;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
	    scanf("%d%d",&x,&y);
	    baga(x,y);
    }
	solve();
	afisare();
	fclose(stdout);
	return 0;
}