Cod sursa(job #3271787)

Utilizator AnSeDraAndrei Sebastian Dragulescu AnSeDra Data 27 ianuarie 2025 12:44:45
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.94 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

const int Nmax = 100005;

struct nod{
    bool vizitat;
    vector<int> vecini;
    vector<int> vecini_transpus;
};

int timp, indice_componenta;
int nr_noduri, nr_muchii, ordine_vizitat[Nmax];
nod graf[Nmax];
vector<int> componente[Nmax];

void citire(){
    int nod1, nod2;

    fin >> nr_noduri >> nr_muchii;

    for(int i = 1; i <= nr_muchii; i++){
        fin >> nod1 >> nod2;

        graf[nod1].vecini.push_back(nod2);
        graf[nod2].vecini_transpus.push_back(nod1);
    }
}

void dfs_marcare_timpi(int nod){
    graf[nod].vizitat = 1;
    ordine_vizitat[++timp] = nod;

    for(int vecin : graf[nod].vecini){
        if(!graf[vecin].vizitat){
            dfs_marcare_timpi(vecin);
        }
    }
}

void resetare_vizitare(){
    for(int i = 1; i <= nr_noduri; i++){
        graf[i].vizitat = 0;
    }
}

void dfs_transpus(int nod){
    graf[nod].vizitat = 1;

    for(int vecin : graf[nod].vecini_transpus){
        if(!graf[vecin].vizitat){
            dfs_transpus(vecin);
        }
    }

    componente[indice_componenta].push_back(nod);
}

void kosaraju(){
    int nod;

    timp = 0;
    for(int i = 1; i <= nr_noduri; i++){
        if(!graf[i].vizitat){
            dfs_marcare_timpi(i);
        }
    }

    resetare_vizitare();
    indice_componenta = 0;
    for(int i = nr_noduri; i >= 1; i--){
        nod = ordine_vizitat[i];
        if(!graf[ordine_vizitat[i]].vizitat){
            indice_componenta++;
            dfs_transpus(nod);
        }
    }
}

void afisare(){
    fout << indice_componenta << '\n';

    for(int i = 1; i <= indice_componenta; i++){
        for(int nod : componente[i]){
            fout << nod << ' ';
        }
        fout << '\n';
    }
}

int main(){
    citire();
    kosaraju();
    afisare();

    return 0;
}