Pagini recente » Cod sursa (job #354963) | Cod sursa (job #720699) | Cod sursa (job #1523956) | Cod sursa (job #2505431) | Cod sursa (job #1414487)
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#include<set>
#include<map>
#include<cmath>
#include<climits>
using namespace std ;
#define maxn 100005
int N, M, nr ;
vector<int> graf[maxn], graftr[maxn], sol[maxn] ;
int lista[maxn] ;
bool sel[maxn] ;
void dfs(int nod)
{
sel[nod] = true ;
for(size_t i = 0; i < graf[nod].size(); ++i)
{
int vecin = graf[nod][i] ;
if( sel[vecin] == false )
dfs(vecin) ;
}
lista[ ++lista[0] ] = nod ;
}
void dfstr(int nod)
{
sel[nod] = true ;
sol[nr].push_back(nod) ;
for(size_t i = 0; i < graftr[nod].size(); ++i)
{
int vecin = graftr[nod][i] ;
if( sel[vecin] == false )
dfstr(vecin) ;
}
}
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 )
dfs(i) ;
memset( sel, 0, sizeof(sel) ) ;
for(int i = N; i > 0; --i)
{
if( sel[ lista[i] ] == false )
{
++nr ;
dfstr( lista[i] ) ;
}
}
printf("%d\n", nr);
for(int i = 1; i <= nr; ++i)
{
for(size_t j = 0; j < sol[i].size(); ++j)
printf("%d ", sol[i][j]);
printf("\n");
}
return 0 ;
}