Pagini recente » Cod sursa (job #2239468) | Cod sursa (job #1704750) | Cod sursa (job #1694628) | Cod sursa (job #1346514) | Cod sursa (job #1250879)
//#include <cstdio>
#include <fstream>
#include <vector>
#define DMAX 100005
#define IN "ctc.in"
#define OUT "ctc.out"
using namespace std;
//FILE*fin=fopen(IN,"r");
//FILE*fout=fopen(OUT,"w");
ifstream fin (IN);
ofstream fout (OUT);
void citire();
void dfs(int);
void dfs_transpus(int);
void gol();
void afisare();
vector <int> A[DMAX], T[DMAX], sol[DMAX];
int uz[DMAX], postordine[DMAX];
int n, m, nr, nrcomp;
int main()
{
int i, j;
citire();
for (i=1; i<=n; i++)
if (!uz[i]) dfs(i);
gol();
for (i=n; i>0; i--)
if (!uz[postordine[i]])
{
nrcomp++;
dfs_transpus(postordine[i]);
//fprintf(fout,"\n");
//fout<<'\n';
}
fout<<nrcomp<<'\n';
for (i=1; i<=nrcomp; i++)
{
for (j=0; j<sol[i].size();j++)
fout<<sol[i][j]<<' ';
fout<<'\n';
}
fout.close();
//fclose(fout);
return 0;
}
void citire()
{
int i, x, y;
//fscanf(fin,"%d %d",&n,&m);
fin>>n>>m;
for (i=1; i<=m; i++)
{
//fscanf(fin,"%d %d",&x,&y);
fin>>x>>y;
A[x].push_back(y);
T[y].push_back(x);
}
}
void dfs(int x)
{
int i;
uz[x]=1;
for (i=0; i<A[x].size(); i++)
if (!uz[A[x][i]])
dfs(A[x][i]);
postordine[++nr]=x;
}
void dfs_transpus(int x)
{
int i;
//fprintf(fout,"%d ",x);
//fout<<x<<' ';
uz[x]=1;
sol[nrcomp].push_back(x);
for (i=0; i<T[x].size(); i++)
if (!uz[T[x][i]])
dfs_transpus(T[x][i]);
}
void gol()
{
for (int i=1; i<=n; i++)
uz[i]=0;
}