Pagini recente » Cod sursa (job #144203) | Cod sursa (job #107697) | Cod sursa (job #66164) | Cod sursa (job #164903) | Cod sursa (job #837102)
Cod sursa(job #837102)
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define maxn 100010
int n, m ;
vector <int> graf[maxn], graftr[maxn], sol[maxn] ;
bool sel[maxn] ;
int lista[maxn], nrlista, nrctc ;
void df(int nod)
{
sel[nod] = true ;
for(size_t i = 0; i < graf[nod].size(); ++i )
{
int nod_act = graf[nod][i] ;
if( sel[ nod_act ] == false )
df( nod_act ) ;
}
lista[ ++nrlista ] = nod;
}
void dftrans(int nod)
{
sel[nod] = true ;
sol[nrctc].push_back(nod) ;
for(size_t i = 0; i < graftr[nod].size(); ++i )
{
int nod_act = graftr[nod][i] ;
if( sel[ nod_act ] == false )
dftrans( nod_act ) ;
}
}
int main()
{
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; ++i )
{
int x, y ;
scanf("%d%d", &x, &y);
graf[x].push_back(y) ;
graftr[y].push_back(x) ;
}
for(int i = 1; i <= n; ++i )
if( sel[i] == false )
df(i) ;
memset( sel, 0, sizeof(sel) ) ;
for(int i = n; i >= 1; --i )
{
if( sel[ lista[i] ] == false )
{
++nrctc ;
dftrans( lista[i] ) ;
}
}
printf("%d\n", nrctc);
for(int i = 1; i <= nrctc; ++i )
{
for(size_t j = 0; j < sol[i].size(); ++j )
printf("%d ", sol[i][j]);
printf("\n");
}
return 0 ;
}