Cod sursa(job #2272207)

Utilizator DordeDorde Matei Dorde Data 29 octombrie 2018 20:31:32
Problema Componente tare conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;
int const NM = 1e5;
vector <int> v [1 + NM] , e;
vector <vector <int> > s;
int stop [1 + NM] , k;
bool viz [1 + NM];
ifstream f ("ctc.in");
ofstream g ("ctc.out");
inline void DF (int node){
    viz [node] = 1;
    for(auto y : v [node])
        if (! viz [y])
            DF (y);
    stop [++ k] = node;
}
inline void flood (int node){
    viz [node] = 1;
    e . push_back (node);
    for(auto i : v [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);
    }
    for(int i = 1 ; i <= n ; ++ i)
        if (! viz [i])
            DF (i);
    fill (viz + 1 , viz + n + 1 , 0);
    for(int i = n ; i > 0 ; -- i)
        if (! viz [i]){
            while (e . size ())
                e . pop_back ();
            flood (i);
            s . push_back (e);
        }
    g << s . size () << '\n';
    for(int i = 0 ; i < s . size () ; ++ i){
        for(auto j : s [i])
            g << j << ' ';
        g << '\n';
    }
    return 0;
}