Cod sursa(job #2543255)

Utilizator GeorgianBaditaBadita Marin-Georgian GeorgianBadita Data 10 februarie 2020 22:58:38
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include<bits/stdc++.h>
#define NMAX 100005

//in-out
std::ifstream f("ctc.in");
std::ofstream g("ctc.out");

//data
std::stack<int> firstDfsSt;
std::vector<int> G[NMAX];
std::vector<int> T[NMAX];
std::vector<int> comps[NMAX];
std::vector<bool> firstDfsViz(NMAX), inComp(NMAX);

int n, m, cnt = 0;

//readData
void readData(){
    f >> n >> m;
    int x, y;
    for(int i = 0; i<m; i++){
        f >> x >> y;
        G[x].push_back(y);
        T[y].push_back(x);
    }
}

void dfsFirst(int start){
    firstDfsViz[start] = true;
    firstDfsSt.push(start);
    for(auto& adj : G[start]){
        if(!firstDfsViz[adj]){
            dfsFirst(adj);
        }
    }
}



void dfsSecond(int start){
    inComp[start] = true;
    comps[cnt].push_back(start);
    for(auto& adj : T[start]){
        if(!inComp[adj]){
            dfsSecond(adj);
        }
    }
    //std::cout << "CNT: " << cnt << "\nWill push back: " << start << '\n';
}

//solve
void solve(){
    for(int i = 1; i<=n; i++){
        if(!firstDfsViz[i]){
            dfsFirst(i);
        }
    }

    while(!firstDfsSt.empty()){
        int node = firstDfsSt.top();
        if(!inComp[node]){
            dfsSecond(node);
            cnt ++;
        }else{
            firstDfsSt.pop();
        }
    }
}

//printSolution
void printSolution(){
    g << cnt << '\n';
    for(int i = 0; i<cnt; i++){
        for(const auto& elem : comps[i]){
            g << elem << ' ';
        }
        g << '\n';
    }
}

int main(){
    readData();
    solve();
    printSolution();
    return 0;
}