Pagini recente » Cod sursa (job #1311418) | Cod sursa (job #2028560) | Cod sursa (job #2196136) | Cod sursa (job #1418418) | Cod sursa (job #834058)
Cod sursa(job #834058)
#include<cstdio>
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std ;
#define maxn 200000
int n, m ;
vector< pair<int, int> > vecini[maxn] ;
bool sel[maxn] ;
bool seltr[maxn] ;
bool elim[maxn] ;
vector<int> sol[maxn] ;
int nrc ;
int nrelim ;
void df_norm(int nod)
{
sel[nod] = true ;
for(size_t i = 0; i < vecini[nod].size(); ++i )
{
int nod_act = vecini[nod][i].first ;
if( vecini[nod][i].second == 1 && sel[ nod_act ] == false && elim[ nod_act ] == false )
df_norm( nod_act ) ;
}
}
void df_trans(int nod)
{
seltr[nod] = true ;
for(size_t i = 0; i < vecini[nod].size(); ++i )
{
int nod_act = vecini[nod][i].first ;
if( vecini[nod][i].second == 2 && seltr[ nod_act ] == false && elim[ nod_act ] == false )
df_trans( 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 a, b ;
scanf("%d%d", &a, &b);
vecini[a].push_back( make_pair(b, 1) ) ;
vecini[b].push_back( make_pair(a, 2) ) ;
}
for(int i = 1; i <= n; ++i )
{
if( elim[i] == false )
{
df_norm( i ) ;
df_trans( i ) ;
++nrc ;
for(int j = 1; j <= n; ++j )
{
if( sel[j] == true && seltr[j] == true )
{
sol[nrc].push_back(j) ;
elim[j] = true ;
++nrelim ;
}
}
if( nrelim == n )
break ;
memset( sel, 0, sizeof(sel) );
memset( seltr, 0, sizeof(seltr) ) ;
}
}
printf("%d\n", nrc);
for(int i = 1; i <= nrc; ++i )
{
for(size_t j = 0; j < sol[i].size(); ++j )
printf("%d ", sol[i][j]);
printf("\n");
}
return 0 ;
}