Pagini recente » Cod sursa (job #764265) | Cod sursa (job #2876249) | Cod sursa (job #1876124) | Cod sursa (job #2884450) | Cod sursa (job #306094)
Cod sursa(job #306094)
#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 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)
{
for (i=last[node];i>=0;i=prev[i])
if (viz[target[i]] && target[i]!=p[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]);
if (b[target[i]]>=b[node])
{
biconexNo++;
if (stack[push]!=i)
{
while (stack[push]!=i)
{
list[size++]=start[stack[push--]];
}
list[size++]=start[stack[push--]];
}
else
{
list[size++]=start[stack[push]];
list[size++]=target[stack[push--]];
}
list[size++]=-1;
}
else
{
b[node]=b[target[i]];
}
}
}
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[i]=x;target[i]=y;prev[i]=last[x];last[x]=i;
}
for (i=0;i<nodeNo;i++)
if (!viz[i]) dfsBiconex(i);
printf("%d\n",biconexNo);
for (i=0;i<size;i++)
if (list[i]==-1)
puts("");
else
printf("%d ",list[i]+1);
fclose(stdout);
return 0;
}