Cod sursa(job #713669)

Utilizator ioalexno1Alexandru Bunget ioalexno1 Data 14 martie 2012 20:40:29
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.88 kb
#include <cstdio>
#define nd 100005
using namespace std;
struct nod{ int val; nod *urm; }*p[nd],*comp[nd];
int tata[nd],niv[nd],low[nd],k,st[5][nd*2],uz[nd],sol;
int n,m;
bool viz[nd],critic[nd];
void read()
{ int i,x,y;
  nod *aux;
freopen("biconex.in","r",stdin); scanf("%d %d\n",&n,&m);
for(i=1;i<=m;++i)
    {
    scanf("%d %d\n",&x,&y);
    aux=new nod; aux->val=y; aux->urm=p[x]; p[x]=aux;
    aux=new nod; aux->val=x; aux->urm=p[y]; p[y]=aux;
    }
fclose(stdin);
}
inline int min(int x,int y)
{
if(x<y)return x; else return y;
return 0;
}
void del(int x,int y)
{ nod *aux;
++sol; ++k;
do
    {
    --k;
    if(uz[st[0][k]]!=sol){
                          aux=new nod; aux->val=st[0][k]; aux->urm=comp[sol]; comp[sol]=aux;
                          uz[st[0][k]]=sol;
                         }
    if(uz[st[1][k]]!=sol)
                        {
                        aux=new nod; aux->val=st[1][k]; aux->urm=comp[sol]; comp[sol]=aux;
                        uz[st[1][k]]=sol;
                        }
    }
while(st[0][k]!=x&&st[1][k]!=y);
--k;
}
void df(int ind)
{ nod *aux;
viz[ind]=1;
for(aux=p[ind];aux!=NULL;aux=aux->urm)
    if(aux->val!=tata[ind])
        {
        if(viz[aux->val]==0)
            {
            ++k; st[0][k]=ind; st[1][k]=aux->val;
            tata[aux->val]=ind; low[aux->val]=niv[aux->val]=niv[ind]+1;
            df(aux->val);
            if(low[aux->val]>=niv[ind])del(ind,aux->val);
            low[ind]=min(low[aux->val],low[ind]);
            }
        else low[ind]=min(low[ind],niv[aux->val]);
        }

}
void write()
{ int i;
  nod *aux;
freopen("biconex.out","w",stdout);
for(i=1;i<=sol;++i)
    {
    for(aux=comp[i];aux!=NULL;aux=aux->urm)
        printf("%d ",aux->val);
    printf("\n");
    }
fclose(stdout);
}
int main()
{
read();
niv[1]=1;
low[1]=0;
sol=0;
df(1);
write();
return 0;
}