Pagini recente » Cod sursa (job #2669848) | Cod sursa (job #1384751) | Cod sursa (job #176280) | Cod sursa (job #164921) | Cod sursa (job #1119412)
#include<cstdio>
#include<vector>
#include<set>
#include<cstring>
using namespace std;
#define MAX 100001
#define pb push_back
int N , M , f[MAX] , k , t ;
vector<int> G[MAX] , Gt[MAX] , C[MAX];
struct comp{
bool operator()(int a , int b)
{
return f[a] > f[b];
}
};
multiset<int,comp> Q;
bool u[MAX];
void read();
void DFS(int nod);
void DFST(int nod);
void write();
void solve();
int main()
{
read();
solve();
write();
return 0;
}
void read()
{
int x , y;
freopen("ctc.in" , "r" , stdin );
scanf("%d%d" , &N , &M );
for(int i = 1 ; i<= M ; ++i )
{
scanf("%d%d" , &x , &y );
G[x].pb(y);
Gt[y].pb(x);
}
}
void solve()
{
for(int i = 1 ; i<= N ; ++i )
if(!u[i])DFS(i);
for(int i = 1 ; i <= N ; ++i )Q.insert(i);
memset(u,0,sizeof(u));
while(!Q.empty())
{
int nod = *Q.begin();
Q.erase(Q.begin());
if(!u[nod])
{
k++;
DFST(nod);
}
}
}
void DFS(int nod)
{
t++;
u[nod] = 1;
for(int i = 0 ; i<(int)G[nod].size() ; ++ i)
if(!u[G[nod][i]])
DFS(G[nod][i]),t++;
f[nod] = t;
}
void DFST(int nod)
{
C[k].pb(nod);
u[nod] = 1;
for(int i = 0 ;i < (int)Gt[nod].size() ; ++i )
if(!u[Gt[nod][i]])
DFST(Gt[nod][i]);
}
void write()
{
freopen("ctc.out" , "w" , stdout );
printf("%d\n" , k );
for(int i = 1 ; i<= k ; ++i )
{
for(int j = 0 ; j < (int)C[i].size() ; ++j )
printf("%d " , C[i][j]);
printf("\n");
}
/* for(int i = 1 ; i <= N ; ++i )
printf("%d " , f[i]);*/
}