Cod sursa(job #3374121)

Utilizator MrbgdBogdan Mrbgd Data 8 noiembrie 2026 18:31:35
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.52 kb
#include <bits/stdc++.h>
using namespace std;

int nr_noduri, nr_muchii;
vector<vector<int>> graf, transpus;
vector<bool> nod_folosit;
vector<int> ordine;
vector<vector<int>> componente;

void dfs1(int nod) {
    nod_folosit[nod] = true;
    for (int urmator : graf[nod])
        if (!nod_folosit[urmator])
            dfs1(urmator);
    ordine.push_back(nod);
}

void dfs2(int nod, vector<int>& componenta) {
    nod_folosit[nod] = true;
    componenta.push_back(nod);
    for (int urmator : transpus[nod])
        if (!nod_folosit[urmator])
            dfs2(urmator, componenta);
}

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

    fin >> nr_noduri >> nr_muchii;
    graf.resize(nr_noduri + 1);
    transpus.resize(nr_noduri + 1);
    for (int i = 0; i < nr_muchii; i++) {
        int x, y;
        fin >> x >> y;
        graf[x].push_back(y);
        transpus[y].push_back(x);
    }
    nod_folosit.assign(nr_noduri + 1, false);
    for (int start = 1; start <= nr_noduri; start++)
        if (!nod_folosit[start])
            dfs1(start);
    nod_folosit.assign(nr_noduri + 1, false);
    for (int i = (int)ordine.size() - 1; i >= 0; i--) {
        int start = ordine[i];
        if (nod_folosit[start]) continue;
        componente.emplace_back();
        dfs2(start, componente.back());
    }
    fout << componente.size() << "\n";
    for (auto& componenta : componente) {
        for (int nod : componenta) fout << nod << " ";
        fout << "\n";
    }
    return 0;
}