Cod sursa(job #2789444)

Utilizator Albert_GAlbert G Albert_G Data 27 octombrie 2021 15:44:59
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>
#include <vector>

std::ifstream in("ctc.in");
std::ofstream out("ctc.out");

const int N = 1e5+1;
std::vector<int> g1[N], g2[N], ctc[N];
int n, m, sortTop[N], cnt, nrCtc;
bool vis[N];

void dfs(int i){
    vis[i] = 1;
    for(auto node : g1[i]){
        if(vis[node]) continue;
        dfs(node);
    }
    sortTop[cnt++] = i;
}

void reset_vis(){
    for(int i=1;i<=n;++i){
        vis[i] = 0;
    }
}

void parcurgere(int i){
    vis[i] = 1;
    for(auto node : g2[i]){
        if(vis[node]) continue;
        parcurgere(node);
    }
    ctc[nrCtc].push_back(i);
}

int main(){
    in>>n>>m;
    for(int i=0;i<m;++i){
        int a,b;
        in>>a>>b;
        g1[a].push_back(b);
        g2[b].push_back(a);
    }
    for(int i=1;i<=n;++i){
        if(vis[i]) continue;
        dfs(i);
    }
    reset_vis();
    for(int i=cnt-1;i>=0;--i){
        if(vis[sortTop[i]]) continue;
        parcurgere(sortTop[i]);
        ++nrCtc;
    }
    out<<nrCtc<<'\n';
    for(int i=0;i<nrCtc;++i){
        for(auto node : ctc[i]){
            out<<node<<' ';
        }
        out<<'\n';
    }
    in.close();
    out.close();
    return 0;
}