Cod sursa(job #1147729)

Utilizator alexalghisiAlghisi Alessandro Paolo alexalghisi Data 20 martie 2014 08:46:51
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#include <bitset>

#define DN  100005
#define pb push_back
#define un unsigned
using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

int n,m,sz;
stack< int > stiva;
bitset< DN > viz;
vector< int > list[DN],t[DN],rez[DN];


void read(){

    f>>n>>m;
    for(;m--;){

        int a,b;
        f>>a>>b;
        list[a].pb(b);
        t[b].pb(a);
    }
}

void dfs(int nod){

    viz[nod] = true;
    for(un int i=0;i<list[nod].size();++i){

        int next_nod = list[nod][i];
        if(!viz[next_nod])
            dfs(next_nod);
    }
    stiva.push(nod);
}

void dfs_t(int nod){

    viz[nod] = true;
    for(un int i=0;i<t[nod].size();++i){

        int next_nod = t[nod][i];
        if(!viz[next_nod])
            dfs_t(next_nod);
    }
    rez[ sz ].pb(nod);
}

void solve(){

    for(int i=1;i<=n;++i)
        if(!viz[i])
            dfs(i);

    viz&=0;
    while(stiva.size()){

        int nod = stiva.top();
        stiva.pop();
        if(!viz[nod]){

            ++sz;
            dfs_t(nod);
        }
    }

}

void write(){

    g<<sz<<"\n";
    for (int i=1;i<=sz;++i){

        for(un int j=0;j<rez[i].size();++j)
            g<<rez[i][j]<<" ";
        g<<"\n";
    }
}
int main()
{
    read();
    solve();
    write();

    return 0;
}