Pagini recente » Cod sursa (job #2058585) | Cod sursa (job #531948) | Cod sursa (job #2029559) | Cod sursa (job #2779049) | Cod sursa (job #1333004)
#include <iostream>
#include <cstdio>
#include <vector>
#include <iterator>
#include <stack>
using namespace std;
const int MAXN = 100000, MAXM = 200000;
int N, M;
vector < vector <int> > G, GT;
void readData()
{
freopen("ctc.in","r",stdin);
scanf("%d %d",&N,&M);
for(int i = 0 ; i <= N; i++)
{
vector <int> aux;
G.push_back(aux);
GT.push_back(aux);
}
for(int i = 1; i <= M; i++)
{
int x, y;
scanf("%d %d",&x,&y);
G[x].push_back(y);
}
}
vector <int> stiva;
int vizitat[MAXN+1];
void dfs(int nod)
{
vizitat[ nod ] = 1;
for(int i = 0; i < G[ nod ].size(); i++)
{
int nextNode = G[ nod ][ i ];
if( vizitat[ nextNode ] == 0 )
dfs( nextNode );
}
stiva.push_back( nod );
}
void construiesteGrafTranspus()
{
for(int i = 0; i <= N; i++)
for(int j = 0 ; j < G[ i ].size(); j++)
{
int node = G[ i ][ j ];
GT[ node ].push_back( i );
}
}
vector <int> deAfisat;
void dfsTranspus(int nod, int k)
{
vizitat[ nod ] = 1;
deAfisat.push_back( nod );
for(int i = 0; i < GT[ nod ].size(); i++)
{
int nextNode = GT[ nod ][ i ];
if( vizitat[ nextNode ] == 0 )
dfsTranspus( nextNode, k );
}
}
int counter = 0;
int main()
{
readData();
for(int i = 1; i <= N; i++)
if( vizitat[ i ] == 0 )
dfs( i );
for(int i = 1; i <= N; i++)
vizitat[ i ] = 0;
construiesteGrafTranspus();
while( stiva.empty() == false )
{
if( vizitat[ stiva[ stiva.size() - 1 ] ] == 0 )
{
counter++;
dfsTranspus( stiva[ stiva.size() - 1 ], counter );
deAfisat.push_back(0);
}
else stiva.pop_back();
}
freopen("ctc.out","w",stdout);
printf("%d\n",counter);
/*
for(int i = 1; i <= counter; i++)
{
for(int j = 1; j <= N && cate[ i ]; j++)
{
if( c[ j ] == i )
{
printf("%d ",j);
cate[ i ]--;
}
}
printf("\n");
}*/
int currentComp = 1;
int index = 0;
for(int i = 1; i <= counter; i++)
{
while( deAfisat[ index ] != 0 )
{
//cout<<deAfisat[ index ]<<' ';
printf("%d ",deAfisat[ index ]);
index++;
}
index++;
//cout<<endl;
printf("\n");
}
return 0;
}