Cod sursa(job #260528)

Utilizator free2infiltrateNezbeda Harald free2infiltrate Data 17 februarie 2009 10:27:54
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <stdio.h>

struct nod
{
int x;
nod *urm;
};
nod *A[100001],*sol[200001];

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

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

void add(int x,int y)
{
nod *urm;
urm = new nod;
urm->x = y;
urm->urm = A[x];
A[x] = urm;
}

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

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

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

void afisare()
{

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

printf("\n");

}

}


int main()
{
freopen("biconex.in","r",stdin);
freopen("biconex.out","wt",stdout);

scanf("%d%d",&n,&m);
int x,y;

while (m)
{
m--;
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}

solve();
afisare();

}