Pagini recente » Cod sursa (job #7649) | Cod sursa (job #334922) | Cod sursa (job #2338042) | Cod sursa (job #407596)
Cod sursa(job #407596)
#include<stdio.h>
#include<vector>
using namespace std;
#define Nmax 100010
vector <int> l[Nmax],lt[Nmax];
int N,v[Nmax],ord[Nmax],K;
int c[Nmax],Nr,comp[Nmax];
void DF(int k)
{
v[k]=1;
for(int i=0;i<(int)l[k].size();++i)
if (!v[ l[k][i] ])
DF( l[k][i] );
++K;
ord[N-K+1]=k;
}
void DFt(int k)
{
v[k]=1;
for(int i=0;i<(int)lt[k].size();++i)
if (!v[ lt[k][i] ])
DFt( lt[k][i] );
c[++K]=k;
}
void solve()
{
for(int i=1;i<=N;++i)
if (!v[i])
DF(i);
K=0;
memset(v,0,sizeof(v));
for(int i=1;i<=N;++i)
if (!v[ ord[i] ])
{
comp[++Nr]=K+1;
DFt(ord[i]);
}
printf("%d\n",Nr);
comp[++Nr]=K+1;
for(int i=1;i<Nr;++i)
{
for(int j=comp[i];j<comp[i+1];++j)
printf("%d ",c[j]);
printf("\n");
}
}
void cit();
int main()
{
cit();
solve();
return 0;
}
void cit()
{
int M,a,b;
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d%d",&N,&M);
for( ; M ;--M)
{
scanf("%d%d",&a,&b);
l[a].push_back(b);
lt[b].push_back(a);
}
}