Pagini recente » Rezultatele filtrării | Cod sursa (job #721656) | Diferente pentru utilizator/neapoleon intre reviziile 3 si 16 | Rezultatele filtrării | Cod sursa (job #2097238)
#include <cstdio>
#include <vector>
#include <bitset>
#include <cstring>
using namespace std;
#define IN "ctc.in"
#define OUT "ctc.out"
#define l 100003
#define pb push_back
bitset<l>viz , ok;
vector<int>G[l],F[l] , SOL[l];
int n , m , lev , sol , k;
int st[l];
void Read()
{
int i , y , x;
scanf ( "%d%d" , &n , &m );
lev = n+1;
for ( i = 1 ; i <= m ; i ++ )
scanf ( "%d%d" , &x , &y ) , G[x].pb(y) , F[y].pb(x);
}
void DFS(int nod)
{
int i;
viz[nod] = 1;
for ( i = 0 ; i < G[nod].size() ; i ++ )
{
if(!viz[G[nod][i]])
DFS(G[nod][i]);
}
st[--lev] = nod;
}
void Fake_DFS(int nod , int k)
{
int i;
ok[nod] = 1;
SOL[k].pb(nod);
for ( i = 0 ; i < F[nod].size() ; i ++ )
{
if(!ok[F[nod][i]])
Fake_DFS(F[nod][i],k);
}
}
void Solve()
{
int j , k = 1 , i;
while ( lev <= n )
{
if(!ok[st[lev]])
sol++ , Fake_DFS(st[lev],k) , k++;
lev++;
}
printf ( "%d\n" , sol );
for ( i = 1 ; i <= k-1 ; i ++ ){
for ( j = 0 ; j < SOL[i].size() ; j ++ )
printf ( "%d " , SOL[i][j] );
printf ("\n");}
}
int main()
{
freopen(IN,"r",stdin);
freopen(OUT,"w",stdout);
Read();
for ( int i = 1 ; i <= n ; i ++ )
if (!viz[i])
DFS(i);
Solve();
}