Pagini recente » Cod sursa (job #1604278) | Cod sursa (job #662086) | Cod sursa (job #99215) | Cod sursa (job #979395) | Cod sursa (job #562200)
Cod sursa(job #562200)
#include<fstream>
#include<cstdio>
#include<vector>
using namespace std;
const int MaxN = 100001;
int n,m,timp=1,nr,tf[MaxN],viz[MaxN],ord[MaxN];
vector<int> G[MaxN],GT[MaxN],CC[MaxN];
void dfs_tf(int nod)
{
vector<int>::iterator it = G[nod].begin(),iend = G[nod].end();
viz[nod] = 1;
for( ; it != iend ; ++it )
if( !viz[*it] )
{
dfs_tf(*it);
++timp;
}
tf[nod] = timp;
}
void ordine()
{
for( int i = 1 ; i <= n ; i++ )
if( !viz[i] )
{
int k = tf[i];
ord[n-k+1] = i;
}
}
void dfst(int nod)
{
vector<int>::iterator it = GT[nod].begin(),iend = GT[nod].end();
viz[nod] = nr;
CC[nr].push_back(nod);
for( ; it != iend ; ++it )
if( !viz[*it] )
dfst(*it);
}
int main()
{
freopen("ctc.in" , "r" , stdin );
freopen("ctc.out" , "w" , stdout );
scanf("%d%d" , &n, &m);
int i,x,y;
for( i = 1 ;i <= m ; i++ )
{
scanf("%d%d" , &x,&y);
G[x].push_back(y);
GT[y].push_back(x);
}
for( i = 1 ; i <= n ; i++ )
if( !viz[i] )
dfs_tf(i);
memset(viz,0,sizeof(viz));
ordine();
for( i = 1 ; i <= n ; i++ )
{
x = ord[i];
if( !viz[x] )
{
nr++;
dfst(x);
}
}
printf("%d\n" , nr);
for( i = 1 ;i <= nr ; i++ )
{
vector<int>::iterator it = CC[i].begin(),iend = CC[i].end();
for( ; it != iend ; ++it )
printf("%d " , *it);
printf("\n");
}
return 0;
}