Cod sursa(job #2097238)

Utilizator VladGhetinaVlad Ghetina VladGhetina Data 30 decembrie 2017 19:30:03
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#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();
}