Pagini recente » Cod sursa (job #1409779) | Cod sursa (job #1088478) | Cod sursa (job #1262495)
#include <cstdio>
using namespace std;
const int N=100001;
const int M=200001;
int lst1[N],urm1[M],vf1[M];
int lst2[N],urm2[M],vf2[M];
bool marcat[N];
int v[N];
int p,nr,ras;
void ad1(int x,int y)
{
p++;
vf1[p]=y;
urm1[p]=lst1[x];
lst1[x]=p;
}
void ad2(int x,int y)
{
p++;
vf2[p]=y;
urm2[p]=lst2[x];
lst2[x]=p;
}
void dfs1(int x)
{
int poz=lst1[x];
marcat[x]=1;
while(poz!=0)
{
if(marcat[vf1[poz]]==0)
dfs1(vf1[poz]);
poz=urm1[poz];
}
v[++nr]=x;
}
void dfs2(int x)
{
int poz=lst2[x];
marcat[x]=1;
while(poz!=0)
{
if(marcat[vf2[poz]]==0)
dfs2(vf2[poz]);
poz=urm2[poz];
}
}
FILE *in,*out;
void dfs3(int x)
{
int poz=lst2[x];
marcat[x]=1;
fprintf(out,"%d ",x);
while(poz!=0)
{
if(marcat[vf2[poz]]==0)
dfs3(vf2[poz]);
poz=urm2[poz];
}
}
int main()
{
in=fopen("ctc.in","r");
out=fopen("ctc.out","w");
int n,m,i,j,x,y,poz;
fscanf(in,"%d%d",&n,&m);
for(i=1;i<=m;i++)
{
fscanf(in,"%d%d",&x,&y);
ad1(x,y);
ad2(y,x);
}
marcat[0]=1;
poz=1;
for(i=1;i<=n;i++)
if(marcat[i]==0)
dfs1(i);
for(i=1;i<=n;i++)
marcat[i]=0;
for(i=n;i>=1;i--)
{
if(marcat[i]==0)
{
ras++;
dfs2(v[i]);
}
}
fprintf(out,"%d\n",ras);
for(i=1;i<=n;i++)
marcat[i]=0;
for(i=n;i>=1;i--)
{
if(marcat[i]==0)
{
dfs3(v[i]);
fprintf(out,"\n");
}
}
return 0;
}