Pagini recente » Cod sursa (job #1581545) | Cod sursa (job #202911) | Cod sursa (job #1738328) | Cod sursa (job #1384345) | Cod sursa (job #562221)
Cod sursa(job #562221)
#include<cstdio>
#include<fstream>
#include<vector>
using namespace std;
const int MaxN = 100001;
int n,m,nrc,end,viz[MaxN],timp[MaxN];
vector<int> G[MaxN],Gt[MaxN],CC[MaxN];
void DFS(int nod)
{
vector<int>::iterator I = G[nod].begin(),IE = G[nod].end();
viz[nod] = 1;
for( ; I != IE ; ++I )
if( !viz[*I] )
DFS(*I);
timp[++end] = nod;
}
void DFSt(int nod)
{
vector<int>::iterator It = Gt[nod].begin(),IEt = Gt[nod].end();
viz[nod] = 1;
CC[nrc].push_back(nod);
for( ; It != IEt ; ++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(i);
memset(viz,0,sizeof(viz));
for( i = n ; i ; i-- )
if( !viz[timp[i]] )
{
nrc++;
DFSt(timp[i]);
}
printf("%d\n" , nrc);
for( i = 1 ; i <= nrc ; i++ )
{
vector<int>::iterator it = CC[i].begin(), iend = CC[i].end();
for( ; it != iend ; ++it )
printf("%d " , *it );
printf("\n");
}
return 0;
}