Cod sursa(job #2982689)

Utilizator sandu_stefanSandu Stefan sandu_stefan Data 20 februarie 2023 18:47:33
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <iostream>
#include <vector>
#include <fstream>

using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
const int NRMAX=10002;
int n,m,nrc;
vector <int>G[NRMAX],GT[NRMAX],
            CTC[NRMAX],Post;
bool viz[NRMAX];
void citire(){
    int x,y;
    f>>n>>m;
    while (m--){
        f>>x>>y;
        G[x].push_back(y);
        GT[y].push_back(x);
    }
}
void dfs(int vf){
    viz[vf]=1;
    for (const auto &x:G[vf]){
        if (!viz[x]){
            dfs(x);
        }
    }
    Post.push_back(vf);
}
void dfsGT(int vf){
    viz[vf]=0;
    CTC[nrc].push_back(vf);
    for (const auto &x:GT[vf]){
        if (viz[x]){
            dfsGT(x);
        }
    }
    Post.push_back(vf);
}
void componente(){
    for (int i=1;i<=n;i++){
        if (!viz[i]){
            dfs(i);
        }
    }
    for (int i=Post.size()-1;i>=0;i--){
        if (viz[Post[i]]){
            ++nrc;
            dfsGT(Post[i]);
        }
    }
}
void afisare(){
    g<<nrc<<'\n';
    for (int i=1;i<=nrc;i++){
        for (int x:CTC[i]){
            g<<x<<' ';
        }
        g<<'\n';
    }
}
int main()
{
    citire();
    componente();
    afisare();
    f.close();
    g.close();
    return 0;
}