Cod sursa(job #3372028)

Utilizator zamhoriaHoria Zamfir zamhoria Data 2 noiembrie 2026 11:58:22
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.54 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream cin("ctc.in");
ofstream cout("ctc.out");

int n, m;

vector<vector<int>> adj;
vector<bool> viz;
vector<vector<int>> componente;
vector<int> ordine; // stiva in care tinem minte nodurile in functie de cand s-a terminat parcurgerea
                    // lor in dfs, pt a face parcurgerea in ordine inversa in cel de-al doilea dfs

void dfs1(int s) {
    viz[s] = true;

    for (auto elem : adj[s]) {
        if (!viz[elem]) {
            dfs1(elem);
        }
    }

    ordine.push_back(s);
}


// functie de inversare a grafului pt parcurgerea in sens invers a grafului original
vector<vector<int>> inversareGraf(int n, vector<vector<int>>& graf) {
    vector<vector<int>> grafInversat(n + 1);

    for (int i = 1; i <= n; i++) {
        for (auto elem : graf[i]) {
            grafInversat[elem].push_back(i);
        }
    }

    return grafInversat;
}

// a doua parcurgere, cea a grafului inversat, in care formam componentele tare conexe
// daca de la un nod putem ajunge la altul si in aceasta parcurgere => aceste 2 noduri fac parte
// dintr-o ctc, deoarece deja am facut parcurgerile in primul sens la primul dfs
void dfs2(int s, vector<int>& componenta, vector<vector<int>>& graf) {
    viz[s] = true;

    componenta.push_back(s);

    for (auto elem : graf[s]) {
        if (!viz[elem]) {
            dfs2(elem, componenta, graf);
        }
    }
}

int main() {

    cin >> n >> m;

    adj.resize(n + 1);
    viz.assign(n + 1, false);

    for (int i = 1; i <= m; i++) {
        int n1, n2;
        cin >> n1 >> n2;
        adj[n1].push_back(n2);
    }

    // prima parcurgere, ne asiguram ca parcurgem toate componentele conexe
    for (int i = 1; i <= n; i++)
        if (!viz[i])
            dfs1(i);

    // resetam vectorul de vizitat, pt cea de a doua parcurgere
    fill(viz.begin(), viz.end(), false);

    // inversam graful pt dfs 2

    vector<vector<int>> grafInversat = inversareGraf(n, adj);

    for (int i = n - 1; i >= 0; i--) {
        int s = ordine[i];

        if (!viz[s]) {
            vector<int> componenta_aux; // componenta tare conexa din care face parte nodul curent

            dfs2(s, componenta_aux, grafInversat);

            componente.push_back(componenta_aux);
        }
    }

    cout << componente.size() << '\n';

    for (auto componenta : componente) {
        for (auto elem : componenta)
            cout << elem << ' ';

        cout << '\n';
    }

    return 0;
}