Cod sursa(job #2489265)

Utilizator mihai2003LLL LLL mihai2003 Data 8 noiembrie 2019 11:00:58
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <cstring>

const int NMAX=100001;
std::vector<int>succ[NMAX],pred[NMAX],sol;
std::vector<std::vector<int> > nrl;
std::ifstream in("ctc.in");
std::ofstream out("ctc.out");
bool viz[NMAX];

void dfs1(int nod){
    viz[nod]=1;
    for(int x:succ[nod])
        if(!viz[x])
            dfs1(x);
    sol.push_back(nod);
}

void dfs2(int nod){
    nrl.back().push_back(nod);
    viz[nod]=1;
    for(int x:pred[nod])
        if(!viz[x])
            dfs2(x);
}

int main(){
    int n,m;
    in>>n>>m;
    for(int i=1,x,y;i<=m;i++)
        in>>x>>y,succ[x].push_back(y),pred[y].push_back(x);
    for(int i=1;i<=n;i++)
        if(!viz[i])
            dfs1(i);
    std::memset(viz,0,sizeof(viz));
    for(int i=sol.size()-1;i>=0;i--)
        if(!viz[sol[i]])
            nrl.push_back(std::vector<int>()),dfs2(sol[i]);
    out<<nrl.size()<<'\n';
    for(int i=0;i<nrl.size();i++,out<<'\n')
        for(int x:nrl[i])
            out<<x<<" ";
    return 0;
}