Cod sursa(job #3374111)

Utilizator Lleonardo211Leonardo-Ioan Leonte Lleonardo211 Data 8 noiembrie 2026 18:07:53
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.85 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");

int N, M;

vector<vector<int>> adiacent;
vector<vector<int>> componenteTC;
vector<bool> vizitat;
vector<int> stiva;

//prima parcurgere DFS
void dfs1(int x) {
    vizitat[x] = true;
    for (auto i : adiacent[x]) {
        if (!vizitat[i]) dfs1(i);
    }
    stiva.push_back(x);
}

//functie inversare muchii
vector<vector<int>> invMuchii(int n, vector<vector<int>>& graf) {
    vector<vector<int>> grafInv(n + 1);
    for (int i = 1; i <= n; i++) {
        for (auto j : graf[i]) {
            grafInv[j].push_back(i);
        }
    }
    return grafInv;
}


//a doua parcurgere DFS, formam componentele tare conexe
void dfs2(int x, vector<int>& componenta, vector<vector<int>>& graf) {
    vizitat[x] = true;
    componenta.push_back(x);
    for (auto i : graf[x]) {
        if (!vizitat[i]) dfs2(i, componenta, graf);
    }
}

int main() {
    fin >> N >> M;
    adiacent.resize(N + 1);
    vizitat.assign(N + 1, false);

    for (int i = 1; i <= M; i++) {
        int x, y;
        fin >> x >> y;
        adiacent[x].push_back(y);
    }

    //Folosind alg lui Kosaraju
    for (int i = 1; i <= M; i++)
        if (!vizitat[i]) dfs1(i);

    //resetam vizitat
    fill(vizitat.begin(), vizitat.end(), false);

    vector<vector<int>> grafInversat = invMuchii(N, adiacent);

    for (int i = N- 1; i >= 0; i--) {
        int x = stiva[i];
        if (!vizitat[x]) {
            vector<int> compTC;
            dfs2(x, compTC, grafInversat);
            componenteTC.push_back(compTC);
        }
    }

    //afisare
    fout << componenteTC.size() << '\n';
    for (auto compTC : componenteTC) {
        for (int x : compTC)
            fout << x << ' ';
        fout << '\n';
    }

    return 0;
}