Cod sursa(job #2276273)

Utilizator DordeDorde Matei Dorde Data 4 noiembrie 2018 15:06:25
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 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 [i])
            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);
    for(int i = 1 ; i <= n ; ++ i)
        viz [i] = 0;
    k = 0;
    for(int i = n ; i > 0 ; -- i)
        if (! viz [stop [i]]){
            comp . clear ();
            flood (stop [i]);
            sol . push_back (comp);
        }
    g << sol . size () << '\n';
    for(auto i : sol){
        for(auto j : i)
            g << j << ' ';
        g << '\n';
    }
    return 0;
}