Cod sursa(job #3003664)

Utilizator Paul281881818818181991919191881818Draghici Paul Paul281881818818181991919191881818 Data 15 martie 2023 20:53:12
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
//tare conex
#include <fstream>
#include <vector>
std::ifstream fin("ctc.in");
std::ofstream fout("ctc.out");
int n;
std::vector<std::vector<int>> V, GT, comp_biconex;
std::vector<int> postorder, viz;
void postDFS(int u){
    viz[u] = true;
    for(auto v : V[u]){
        if(!viz[v]){
            postDFS(v);
        }
    }
    postorder.push_back(u);
}
int cnt;
void DFS(int u){
    viz[u] = true;
    comp_biconex[cnt].push_back(u);
    for(auto v : GT[u]){
        if(!viz[v]){
            DFS(v);
        }
    }
}
int main(){
    int n, m;
    fin >> n >> m;
    V = GT = comp_biconex = std::vector<std::vector<int>> (n + 1, std::vector<int> ());
    viz = std::vector<int> (n + 1, 0);
    for(int u, v, i = 1; i <= m; i++){
        fin >> u >> v;
        V[u].push_back(v);
        GT[v].push_back(u);
    }
    for(int i = 1; i <= n; i++){
        if(!viz[i]){
            postDFS(i);
        }
    }
    viz = std::vector<int> (n + 1, 0);
    for(int i = n - 1; i > 0; i--){
        if(!viz[postorder[i]]){
            DFS(postorder[i]);
            ++cnt;
        }
    }
    fout << cnt << "\n";
    for(int i = 0; i < cnt; i++){
        for(auto it : comp_biconex[i])
            fout << it << " ";
        fout << "\n";
    }
}