Cod sursa(job #3373329)

Utilizator ilinca_onofreiIlinca-Ioana Onofrei ilinca_onofrei Data 6 noiembrie 2026 16:43:57
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.65 kb
#include <iostream>
#include <fstream>
#include <vector>

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

const int MAXN = 100005;
vector<int> adiacenta[MAXN];
vector<int> adiacenta_transpusa[MAXN];

bool vizitat[MAXN];
vector<int> stiva_ordine;
vector<vector<int>> componente;
vector<int> componenta_curenta;

void dfs(int u) {
    vizitat[u] = true;
    for (int vecin : adiacenta[u]) {
        if (!vizitat[vecin]) {
            dfs(vecin);
        }
    }
    stiva_ordine.push_back(u);
}

void dfs_transpus(int u) {
    vizitat[u] = true;
    componenta_curenta.push_back(u);

    for (int vecin : adiacenta_transpusa[u]) {
        if (!vizitat[vecin]) {
            dfs_transpus(vecin);
        }
    }
}

int main() {

    int n, m;
    if (!(fin >> n >> m)) return 0;

    for (int i = 0; i < m; ++i) {
        int x, y;
        fin >> x >> y;
        adiacenta[x].push_back(y);
        adiacenta_transpusa[y].push_back(x);
    }

    for (int i = 1; i <= n; ++i) {
        if (!vizitat[i]) {
            dfs(i);
        }
    }

    for (int i = 1; i <= n; ++i) {
        vizitat[i] = false;
    }

    for (int i = (int)stiva_ordine.size() - 1; i >= 0; --i) {
        int nod = stiva_ordine[i];
        if (!vizitat[nod]) {
            componenta_curenta.clear();
            dfs_transpus(nod);
            componente.push_back(componenta_curenta);
        }
    }

    fout << componente.size() << "\n";
    for (const auto& comp : componente) {
        for (size_t i = 0; i < comp.size(); ++i) {
            fout << comp[i] << (i + 1 == comp.size() ? "" : " ");
        }
        fout << "\n";
    }

    fin.close();
    fout.close();
    return 0;
}