Pagini recente » Cod sursa (job #1077596) | Cod sursa (job #981136) | Cod sursa (job #2965297) | Cod sursa (job #2546414) | Cod sursa (job #644904)
Cod sursa(job #644904)
#include<fstream>
#include<vector>
using namespace std;
FILE *g=fopen("ctc.out","w");
int i,j,n,m,viz[100002],t,ord[100002],x,y,cr=0,nr=0;
vector<int> a[100002];
vector<int> at[100002];
vector<int> d[100002];
void dfs(int x)
{
int i;
viz[x]=1;
for(i=0;i<a[x].size();++i)
if(!viz[a[x][i]])
dfs(a[x][i]);
ord[++cr]=x;
}
void dfst(int x)
{
int i;
viz[x]=0;
d[nr].push_back(x);
//fprintf(g,"%d ",x);
for(i=0;i<at[x].size();++i)
if(viz[at[x][i]])
dfst(at[x][i]);
}
int main()
{
FILE *f=fopen("ctc.in","r");
fscanf(f,"%d%d",&n,&m);
for(i=1;i<=m;++i)
{
fscanf(f,"%d%d",&x,&y);
a[x].push_back(y);
at[y].push_back(x);
}
for(i=1;i<=n;++i)
if(!viz[i])
dfs(i);
for(i=n;i>=1;--i)
if(viz[ord[i]])
{
++nr;
dfst(ord[i]);
}
fprintf(g,"%d\n",nr);
for(i=1;i<=nr;++i)
{
for(j=0;j<d[i].size();++j)
fprintf(g,"%d ",d[i][j]);
fprintf(g,"\n");
}
return 0;
}