Pagini recente » Cod sursa (job #1466895) | Cod sursa (job #2439716) | Cod sursa (job #2589129) | Cod sursa (job #42438) | Cod sursa (job #497935)
Cod sursa(job #497935)
#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 , v;
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]);
top[++v] = 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);
}
memset(seen,0,sizeof(seen));
for( i = n ; i >= 1 ; --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;
}