Cod sursa(job #3264390)

Utilizator Luijika_programatorulBursuc Luigi Luijika_programatorul Data 20 decembrie 2024 22:13:52
Problema Componente tare conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include<bits/stdc++.h>
auto in = std::freopen("ctc.in" , "r" , stdin);
auto out = std::freopen("ctc.out" , "w" , stdout);
#define fast std::ios_base::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);
int n,m;
std::vector<int> g[100005] , gt[100005];
std::stack<int> pst;
int c[100005];
int cc;
bool viz[100005];
std::vector<int> scc[100005];
void dfs1(int nod){
    for(auto f : g[nod]){
        if(!viz[f]){
            viz[f]=1;
            dfs1(f);
        }
    }
    pst.push(nod);
}

void dfs2(int nod){
    c[nod] = cc;
    scc[cc].push_back(nod);
    for(auto f : gt[nod]){
        if(!viz[f]){
            viz[f] = 1;
            dfs2(f);
        }
    }
}


int main(){
    fast;
    std::cin >> n >> m;
    for(int i=1,u,v;i<=m;++i){
        std::cin >> u >> v;
        g[u].push_back(v);
        gt[v].push_back(u);
    }
    for(int i=1;i<=n;++i){
        if(!viz[i]){
            viz[i] =1;
            dfs1(i);
        }
    }

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

    for(int i=1;i<=n;++i){
        if(!viz[i]){
            viz[i] = 1;
            dfs2(i),cc++;
        }
    }


    std::cout << cc <<"\n";
    for(int i=0;i<cc;++i){
        for(auto x : scc[i])std::cout << x <<' ';
        std::cout << "\n";
    }
    return 0;
}