Pagini recente » Cod sursa (job #2646154) | Cod sursa (job #2793908) | Cod sursa (job #2484273) | Cod sursa (job #60765) | Cod sursa (job #1262530)
#include <stdio.h>
using namespace std;
const int N=100001;
const int M=200001;
bool v[N];
int lst[2][N],nod[2][M],nxt[2][M],smen[N],rez[2*N];
int nr[2],n,m,nsmen,vf,nc,nrez;
void adauga(int e, int x, int y)
{
nr[e]++;
nod[e][nr[e]]=y;
nxt[e][nr[e]]=lst[e][x];
lst[e][x]=nr[e];
}
void dfs(int x)
{
int p;
v[x]=1;
p=lst[0][x];
while(p!=0)
{
if(!v[nod[0][p]])
dfs(nod[0][p]);
p=nxt[0][p];
}
smen[nsmen++]=x;
}
void dfsmen(int x)
{
int p;
v[x]=1;
rez[nrez++]=x;
//printf("%d ",x);
p=lst[1][x];
while(p!=0)
{
if(!v[nod[1][p]])
dfsmen(nod[1][p]);
p=nxt[1][p];
}
}
int main()
{
FILE *in,*out;
in=fopen("ctc.in","r");
out=fopen("ctc.out","w");
int i,x,y;
fscanf(in,"%d%d",&n,&m);
for(i=0;i<m;i++)
{
fscanf(in,"%d%d",&x,&y);
adauga(0,x,y);
adauga(1,y,x);
}
for(i=1;i<=n;i++)
if(!v[i])
dfs(i);
for(i=1;i<=n;i++)
v[i]=0;
for(i=nsmen-1;i>=0;i--)
{
vf=smen[i];
if(!v[vf])
{
dfsmen(vf);
nc++;
rez[nrez++]=-1;
//printf("\n");
}
}
fprintf(out,"%d\n",nc);
for(i=0;i<nrez;i++)
{
if(rez[i]==-1)
fprintf(out,"\n");
else
fprintf(out,"%d ",rez[i]);
}
return 0;
}