Pagini recente » Borderou de evaluare (job #1582007) | Cod sursa (job #505201) | Cod sursa (job #1836230) | Cod sursa (job #2165977) | Cod sursa (job #306109)
Cod sursa(job #306109)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define VMAX 110000
#define EMAX 210000
#define MINIM(a,b) a<b?a:b
int start[EMAX],target[EMAX],prev[EMAX],last[VMAX],stack[EMAX],list[EMAX*2],p[VMAX],d[VMAX],b[VMAX];
char used[VMAX];
char viz[VMAX];
int edgeNo,nodeNo,push=0,size=0,timp=0,biconexNo=0;
void dfsBiconex(int node)
{
viz[node]=1;
int i;
d[node]=++timp;
b[node]=d[node];
if (last[node]!=-1 || timp!=1)
{
for (i=last[node];i>=0;i=prev[i])
if (target[i]!=p[node])
{
if (viz[target[i]]&&d[target[i]]<d[node])
{
stack[++push]=i;
b[node]=MINIM(b[node],d[target[i]]);
}
else if (!viz[target[i]])
{
p[target[i]]=node;
stack[++push]=i;
dfsBiconex(target[i]);
b[node]=MINIM(b[node],b[target[i]]);
if (b[target[i]]>=d[node])
{
biconexNo++;
if (stack[push]!=i)
{
memset(used,'\0',VMAX);
while (stack[push]!=i)
{
if (!used[start[stack[push]]])
{
used[start[stack[push]]]=1;
list[size++]=start[stack[push--]];
}
else push--;
}
if (!used[start[stack[push]]]) list[size++]=start[stack[push--]];
}
else
{
list[size++]=start[stack[push]];
list[size++]=target[stack[push--]];
}
list[size++]=-1;
}
}
}
}
else
{
biconexNo++;
list[size++]=node;
list[size++]=-1;
}
timp--;
}
int main()
{
int i,x,y;
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
scanf("%d %d",&nodeNo,&edgeNo);
for (i=0;i<nodeNo;i++) last[i]=-1;
for (i=0;i<nodeNo;i++) p[i]=-1;
for (i=0;i<edgeNo;i++)
{
scanf("%d %d",&x,&y);x--;y--;
start[2*i]=x;target[2*i]=y;prev[2*i]=last[x];last[x]=2*i;
start[2*i+1]=y;target[2*i+1]=x;prev[2*i+1]=last[y];last[y]=2*i+1;
}
for (i=0;i<nodeNo;i++)
if (!viz[i]) dfsBiconex(i);
printf("%d\n",biconexNo);
for (i=size-2;i>=0;i--)
if (list[i]==-1)
puts("");
else
printf("%d ",list[i]+1);
fclose(stdout);
return 0;
}