Pagini recente » Cod sursa (job #1080254) | Cod sursa (job #2502305) | Cod sursa (job #296691) | Cod sursa (job #28556) | Cod sursa (job #250939)
Cod sursa(job #250939)
#include<stdio.h>
#include<string.h>
#define Nmax 100003
#define Mmax 200002
#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],viz[Nmax], nrf[Nmax], low[Nmax];
inline void insert(int x, int y)
{
Nod *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][Mmax];
int nr;
int sol[Nmax];
Nod *S[Nmax];
void ins(int x, int y)
{
Nod *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] >= low[nod]) elim(nod, q->info);
low[nod]=min(low[nod],low[q->info]);
}
else low[nod]=min(low[nod],low[q->info]);
}
}
int main()
{
read();
memset(df,-1,sizeof(df));
dfs(1,0,0);
print();
return 0;
}