Pagini recente » Cod sursa (job #2205587) | Cod sursa (job #143863) | Monitorul de evaluare | Cod sursa (job #155874) | Cod sursa (job #306039)
Cod sursa(job #306039)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define VMAX 100010
#define EMAX 310000
int start[EMAX],target[EMAX],prev[EMAX],last[VMAX],list[VMAX],ctc[VMAX];
char viz[VMAX];
int edgeNo,nodeNo,push,ctcNo=0;
void dfs(int node)
{
viz[node]=1;
int i;
for (i=last[node];i>=0;i=prev[i])
if (!viz[target[i]]) dfs(target[i]);
list[push--]=node;
}
void dfs2(int node)
{
viz[node]=1;
int i;
for (i=last[node];i>=0;i=prev[i])
if (!viz[target[i]]) dfs2(target[i]);
ctc[push++]=node+1;
}
int main()
{
int i,x,y;
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d %d",&nodeNo,&edgeNo);
for (i=0;i<nodeNo;i++) last[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;
}
push=nodeNo-1;
for (i=0;i<nodeNo;i++)
if (!viz[i]) dfs(i);
for (i=0;i<nodeNo;i++) last[i]=-1;
for (i=0;i<nodeNo;i++) viz[i]=0;
for (i=0;i<edgeNo;i++)
{
x=start[i];start[i]=target[i];target[i]=x;
prev[i]=last[start[i]];
last[start[i]]=i;
}
push=0;
for (i=0;i<nodeNo;i++)
if (!viz[list[i]])
{
dfs2(list[i]);
ctcNo++;
ctc[push++]=-1;
}
printf("%d\n",ctcNo);
for (i=0;i<push;i++)
{
if (ctc[i]==-1)
puts("");
else
printf("%d ",ctc[i]);
}
fclose(stdout);
return 0;
}