Pagini recente » Cod sursa (job #2834600) | Cod sursa (job #3127995) | Cod sursa (job #518338) | Cod sursa (job #2802195) | Cod sursa (job #1833598)
#include <cstdio>
#include <stack>
#include <vector>
#define mmax 200001
const int nmax=1000000;
using namespace std;
FILE *f, *g;
int n,m;
bool viz[nmax];
bool viz1[nmax];
vector <int> V[mmax];
vector <int> V1[mmax];
vector <int> Vt[mmax];
stack <int> S;
void read()
{ int i,x,y;
fscanf(f,"%d%d",&n,&m);
for(i=1;i<=m;++i)
{ fscanf(f,"%d%d",&x,&y);
/* fprintf(g,"%d ",x);
fprintf(g,"%d",y);
fprintf(g,"\n"); */
V[x].push_back(y);
Vt[y].push_back(x);
}
fclose(f);
}
void dfs(int x)
{ int i;
vector <int>::iterator it;
viz[x]=1;
for(it=V[x].begin();it!=V[x].end();++it)
if(!viz[*it]) dfs(*it);
S.push(x);
}
void dfs2(int x, int nr)
{ int i;
vector <int>::iterator it;
viz1[x]=1;
for(it=Vt[x].begin();it!=Vt[x].end();++it)
if(!viz1[*it]) dfs2(*it,nr);
V1[nr].push_back(x);
}
int main()
{
f=fopen("ctc.in","r");
g=fopen("ctc.out","w");
read();
for(int i=1;i<=n;i++)
if(!viz[i]) dfs(i);
int x,nr=0;
while(!S.empty())
{ x=S.top();
S.pop();
if(!viz1[x]){nr++;
dfs2(x,nr);}
}
fprintf(g,"%d",nr);
fprintf(g,"\n");
vector <int>::iterator it;
for(int i=1;i<=n;i++)
{for(it=V1[i].begin();it!=V1[i].end();++it)
fprintf(g,"%d ",*it);
fprintf(g,"\n");
}
return 0;
}