Cod sursa(job #633358)

Utilizator VladberilaVladutz Vladberila Data 13 noiembrie 2011 17:40:19
Problema Componente biconexe Scor 52
Compilator cpp Status done
Runda Arhiva educationala Marime 2.29 kb
#include <stdio.h>
#define Nmax 100001
#define Mmax 200001
int n,m,dfn[Nmax],low[Nmax],vf,nr,nrfii,Fiu[Nmax];
struct nod1
{
    int x;
    nod1 *urm;
}*Sol[Nmax];
struct
{
    int t,f;
}S[Mmax];
struct nod
{
    int info;
    nod *urm;
} *l[Nmax];
inline int min(int a,int b)
{
    return a<b?a:b;
}
void add(nod *&p,int x)
{
    nod *q=new nod;
    q->info=x;
    q->urm=p;
    p=q;
}
void add(nod1 *&p,int x)
{
    nod1 *q=new nod1;
    q->x=x;
    q->urm=p;
    p=q;
}
void citire()
{
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    scanf("%d%d",&n,&m);
    int i,x,y;
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        add(l[x],y);
        add(l[y],x);
    }
}
void init(int start)
{
    int i;
    for(i=1;i<=n;i++)
       dfn[i]=low[i]=-1;
    S[0].f=start;
    S[0].t=-1;
    vf=0;
}
void Conex(int x,int u)
{
    int p,k;
    nr++;
    do
    {
        p=S[vf].f;
        k=S[vf].t;
        vf--;
        add(Sol[nr],p);
        add(Sol[nr],k);
    }
    while(p!=x || k!=u);
}
void dfs(int u,int tu,int niv)
{
    //u vf curent, tu tatal lui u, niv nivelul curent
    //dfn[x]=nr de ordine al vf x in parcurgerea DFS
    //low[x]=nr de ordine al primului vf din parcurgerea DFS ce poate fi atins din x
    //pe un alt lant decat lantul unic din arb partial DFS
    dfn[u]=low[u]=niv;
    int x;
    nod *q;
    for(q=l[u];q;q=q->urm)
    {
        x=q->info;
        if(x!=tu) //x nu e tatal lui u
           if(dfn[x]!=-1) // si nodul x e vizitat
               low[u]=min(low[u],dfn[x]); //deci [u,x] m de intoarcere
           else //nodul x e nevizitat
           {
               //pun in stiva muchia [u,x]
               vf++;
               S[vf].f=x;
               S[vf].t=u;
               dfs(x,u,niv+1);
               low[u]=min(low[x],low[u]);
               if(low[x]>=dfn[u])
                  Conex(x,u);
           }
    }
}
int main()
{
    int i,c;
    citire();
    init(1);
    dfs(1,-1,1);
    printf("%d\n",nr);
    for(i=1;i<=nr;i++)
    {
        c=0;
        for(nod1 *p=Sol[i];p;p=p->urm)
           if(p->x!=c)
           {
               printf("%d ",p->x);
               c=p->x;
           }
        printf("\n");
    }
    return 0;
}