Pagini recente » Cod sursa (job #667183) | Cod sursa (job #767346) | Cod sursa (job #1380032) | Cod sursa (job #61181) | Cod sursa (job #497855)
Cod sursa(job #497855)
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
const int maxn = 100005;
using namespace std;
int i , j , k , t[maxn] , a , b , n , m , top[maxn] , ans;
vector <int> G[maxn] , G2[maxn] , L[maxn];
bool seen[maxn];
struct cmp { bool operator () ( const int &a , const int &b ) {
return (t[a] > t[b] );
}
};
void DF1 (int node)
{
int i;
seen[node] = 1;
for( i = 0 ; i < G2[node].size() ; ++i ) {
if ( !seen[G2[node][i]])
DF1(G2[node][i]);
t[node] = max ( t[node] , t[G2[node][i]]) ;
}
if ( G2[node].size() ) t[node]++;
}
void DF2( int node ) {
int i;
seen[node] = 1;
L[ans].push_back(node);
for( i = 0 ; i < G[node].size() ; ++i )
if ( !seen[G[node][i]])
DF2(G[node][i]);
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d %d",&n,&m);
for( i = 1 ; i <= m ; ++i ) {
scanf("%d %d",&a,&b);
G[a].push_back(b);
G2[b].push_back(a);
}
for( i = 1 ; i <= n ; ++i )
t[i] = 0;
for( i = 1 ; i <= n ; ++i ) {
if ( !seen[i] )
DF1(i);
top[i] = i;
}
memset( seen , 0 , sizeof(seen));
sort ( top + 1, top + n + 1 , cmp());
for( i = 1 ; i <= n ; ++i ) {
if ( !seen[top[i]]) {
ans ++;
DF2(top[i]);
}
}
printf("%d\n",ans);
for( i = 1 ; i <= ans ; ++i ) {
for( j = 0 ; j < L[i].size() ; ++j)
printf("%d ",L[i][j]);
printf("\n");
}
return 0;
}