Cod sursa(job #2617091)

Utilizator adiaioanaAdia R. adiaioana Data 20 mai 2020 18:32:42
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <fstream>
#include <vector>
#include <list>
#define NMAX 100100
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
int N,M, vis1[NMAX], vis2[NMAX], mark;
vector <int> Ginit[NMAX], G_inv[NMAX];
inline void scan() {
    int x,y;
    cin>>N>>M;
    for(int i=1; i<=M; ++i) {
        cin>>x>>y;
        Ginit[x].push_back(y);
        G_inv[y].push_back(x);
    }
}
list <int> List;
inline void dfsmth(int x) {

    vis1[x]=1;
    for(auto it:Ginit[x])
        if(!vis1[it])
            dfsmth(it);
    List.push_back(x);
}

void dfmark(int x, int smth) {

    vis2[x]=smth;
    for(auto it: G_inv[x])
        if(!vis2[it])
            dfmark(it, smth);
}

vector <int> compcon[NMAX];
inline void print() {

    cout<<mark<<'\n';
    for(int i=1; i<=mark; ++i, cout<<'\n')
        for(int j=0; j<compcon[i].size(); ++j)
            cout<<compcon[i][j]<<' ';
}
int main()
{
    scan();

    for(int i=1; i<=N; ++i)
        if(!vis1[i])
            dfsmth(i);

    while(!List.empty()) {
        int el=List.back();
        if(!vis2[el])
            dfmark(el,++mark);
        List.pop_back();
    }

    for(int i=1; i<=N; ++i)
        compcon[vis2[i]].push_back(i);
    print();
    return 0;
}