Pagini recente » Cod sursa (job #1898556) | Cod sursa (job #2334541) | Cod sursa (job #2143927) | Cod sursa (job #2218712) | Cod sursa (job #555755)
Cod sursa(job #555755)
#include<stdio.h>
#include<vector>
#define Nmax 100010
using namespace std;
int n,m,viz[Nmax],i,a,b,ctc,S[Nmax],nn,N,j;
vector<int> G[Nmax],T[Nmax],Ctc[Nmax];
void sortaret ( int nod )
{
int i, N = G[nod].size() ;
viz[nod] = 1 ;
for( i = 0 ; i < N ; i++ )
if( !viz[ G[nod][i] ] ) sortaret( G[nod][i] ) ;
S[--nn] = nod ;
}
void dfs ( int nod )
{
int i, N = T[nod].size() ;
Ctc[ctc].push_back(nod);
viz[nod] = 0 ;
for( i = 0 ; i < N ; i++ )
if( viz[ T[nod][i] ] ) dfs( T[nod][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);
T[b].push_back(a);
}
nn = n + 1 ;
for( i = 1 ; i <= n ; i++ )
if( !viz[i] ) sortaret(i);
for( i = 1 ; i <= n ; i++ )
if( viz[ S[i] ] ) ctc++, dfs( S[i] ) ;
printf("%d\n",ctc);
for( i = 1 ; i <= ctc ; i++ )
{
N = Ctc[i].size();
for( j = 0 ; j < N ; j++ )
printf("%d ",Ctc[i][j]);
printf("\n");
}
return 0 ;
}