Cod sursa(job #2276265)

Utilizator DordeDorde Matei Dorde Data 4 noiembrie 2018 14:57:49
Problema Componente tare conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <fstream>
#include <vector>
#include <bitset>
using namespace std;
ifstream f ("ctc.in");
ofstream g ("ctc.out");
int const NM = 1e5;
vector <int> v [1 + NM] , comp , v2 [1 + NM];
vector <vector <int>> sol;
bitset <1 + NM> viz;
int stop [1 + NM] , k;
void DF (int node){
    viz [node] = 1;
    for(auto i : v [node])
        if (! viz [node])
            DF (i);
    stop [++ k] = node;
}
void flood (int node){
    viz [node] = 1;
    comp . push_back (node);
    for(auto i : v2 [node])
        if (! viz [i])
            flood (i);
}
int main()
{
    int n , m;
    f >> n >> m;
    for(int i = 1 ; i <= m ; ++ i){
        int a , b;
        f >> a >> b;
        v [a] . push_back (b);
        v2 [b] . push_back (a);
    }
    for(int i = 1 ; i <= n ; ++ i)
        if (! viz [i])
            DF (i);
    while (k --)
        viz [k + 1] = 0;
    k = 0;
    for(int i = 1 ; i <= n ; ++ i)
        if (! viz [stop [i]]){
            flood (stop [i]);
            sol . push_back (comp);
            while (comp . size ())
                comp . pop_back ();
        }
    g << sol . size () << '\n';
    for(auto i : sol){
        for(auto j : i)
            g << j << ' ';
        g << '\n';
    }
    return 0;
}