Pagini recente » Cod sursa (job #1080196) | Cod sursa (job #3287305) | Rating manea georege caharisitan (georgie) | Cod sursa (job #1416031) | Cod sursa (job #1411882)
#include<bits/stdc++.h>
#define Nmax 100005
#define IT vector < int > :: iterator
using namespace std;
int N, M, Nr_CTC;
vector < int > G[Nmax], G_t[Nmax], St[Nmax], aux;
bool viz[Nmax];
void dfs_G(int Nod)
{
viz[Nod] = 1;
for(IT it = G[Nod].begin(); it != G[Nod].end(); ++ it)
if(!viz[*it])
dfs_G(*it);
aux.push_back(Nod);
}
void dfs_G_t(int Nod)
{
St[Nr_CTC].push_back(Nod);
viz[Nod] = 0;
for(IT it = G_t[Nod].begin(); it != G_t[Nod].end(); ++ it)
if(viz[*it])
dfs_G_t(*it);
}
void Read()
{
freopen("ctc.in", "r", stdin);
scanf("%d%d", &N, &M);
for( ; M; -- M) {
int X, Y;
scanf("%d %d", &X, &Y);
G[X].push_back(Y);
G_t[Y].push_back(X);
}
}
void Write()
{
freopen("ctc.out", "w", stdout);
printf("%d\n", Nr_CTC);
for( ; Nr_CTC; printf("\n"), -- Nr_CTC)
for(IT it = St[Nr_CTC].begin(); it != St[Nr_CTC].end(); ++ it)
printf("%d ", *it);
}
void Solve()
{
for(int i = 1; i <= N; ++ i)
if(!viz[i])
dfs_G(i);
for(IT it = aux.end() - 1; it >= aux.begin(); -- it)
if(viz[*it])
Nr_CTC ++, dfs_G_t(*it);
}
int main()
{
Read();
Solve();
Write();
return 0;
}