Pagini recente » Cod sursa (job #1535003) | Cod sursa (job #717731) | Cod sursa (job #3206594) | Cod sursa (job #756765) | Cod sursa (job #1303483)
#include <iostream>
#include <cstdio>
#include <vector>
#define nmax 100001
using namespace std;
FILE *f=fopen("ctc.in","r"),*g=fopen("ctc.out","w");
int postord[nmax],viz[nmax],n,lg,t;
vector <int> l[nmax],lt[nmax],r[nmax];
void df(int k)
{
int i,x;
viz[k]=1;
for(i=0;i<l[k].size();i++)
{
x=l[k][i];
if(!viz[x])
df(x);
}
postord[++lg]=k;
}
void dft(int k)
{
int i,x;
r[t].push_back(k);
viz[k]=0;
for(i=0;i<lt[k].size();i++)
{
x=lt[k][i];
if(viz[x])
dft(x);
}
}
int main()
{
int i,j,m,x,y;
fscanf(f,"%d %d",&n,&m);
for(i=1;i<=m;i++)
{
fscanf(f,"%d %d",&x,&y);
l[x].push_back(y);
lt[y].push_back(x);
}
for(i=1;i<=n;i++)
if(!viz[i])
df(i);
for(i=n;i>=1;i--)
if(viz[postord[i]])
{
++t;
dft(postord[i]);
}
fprintf(g,"%d\n",t);
for(i=1;i<=t;i++)
{
for(j=0;j<r[i].size();j++)
fprintf(g,"%d ",r[i][j]);
fprintf(g,"\n");
}
return 0;
}