Pagini recente » Cod sursa (job #2755104) | Cod sursa (job #3212104) | Cod sursa (job #3201793) | Cod sursa (job #2383522) | Cod sursa (job #250961)
Cod sursa(job #250961)
#include<stdio.h>
#include<string.h>
#define Nmax 100005
#define min(a,b) ((a)<(b)?(a):(b))
FILE*f=fopen("biconex.in","r");
FILE*g=fopen("biconex.out","w");
struct Nod
{
int info;
Nod *urm;
};
Nod *prim[Nmax];
int n,df[Nmax],low[Nmax];
inline void insert(int x, int y)
{
Nod *p;
p=new Nod;
p->info=x;
p->urm=prim[y];
prim[y]=p;
}
void read()
{
int m,x,y;
fscanf(f,"%d %d",&n,&m);
while(m--)
{
fscanf(f,"%d %d",&x,&y);
insert(x,y);
insert(y,x);
}
}
int vf,st[2][Nmax];
int nr;
int sol[Nmax];
Nod *S[Nmax];
inline void ins(int x, int y)
{
Nod *q;
q=new Nod;
q->info=y;
q->urm=S[x];
S[x]=q;
}
void print()
{
int i;
Nod *q;
fprintf(g,"%d\n",nr);
for(i=1;i<=nr;++i)
{
for(q=S[i];q;q=q->urm)
fprintf(g,"%d ",q->info);
fprintf(g,"\n");
}
}
void elim(int x, int y)
{
nr++;
do
{
if(sol[st[0][vf]]!=nr)
{
sol[st[0][vf]]=nr;
ins(nr, st[0][vf]);
}
if(sol[st[1][vf]]!=nr)
{
sol[st[1][vf]]=nr;
ins(nr,st[1][vf]);
}
--vf;
}
while(st[0][vf+1] != x || st[1][vf+1] != y);
}
void dfs(int nod, int T, int niv)
{
Nod *q;
low[nod]=df[nod]=niv;
for(q=prim[nod];q;q=q->urm)
{
if ( q->info == T ) continue;
if ( df[q->info] == -1 )
{
st [ 0 ][ ++vf ] = nod; st [ 1 ] [ vf ] = q->info;
dfs ( q->info , nod , niv+1 );
if(low[ q->info ] >= df[ nod ] ) elim( nod, q->info );
low [ nod ] = min ( low[nod],low[ q->info ] );
}
else low[nod]=min (low[nod] , df[q->info]);
}
}
int main()
{
read();
memset(df,-1,sizeof(df));
nr=0; vf=0;
dfs(1,0,0);
print();
return 0;
}