Cod sursa(job #3371003)

Utilizator vik4torTunaru Victor-Cristian vik4tor Data 28 octombrie 2026 11:27:03
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <bitset>
#include <fstream>
#include <vector>

using namespace std;

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

vector<vector<int>> graf;
vector<vector<int>> graf_transpus;
vector<vector<int>> ctc;
vector<int> f;

constexpr int NMAX = 100005;
bitset<NMAX> vizitat;

int nr_ctc = 0;

void dfs_normal(int nod) {
    vizitat[nod] = true;
    for (int next : graf[nod]) {
        if (!vizitat[next]) {
            dfs_normal(next);
        }
    }
    f.push_back(nod);
}

void dfs_transpusa(int nod, vector<int>& comp) {
    vizitat[nod] = true;
    comp.push_back(nod);
    for (int next : graf_transpus[nod]) {
        if (!vizitat[next]) {
            dfs_transpusa(next, comp);
        }
    }
}

int main() {
    int N, M, X, Y;
    if (!(fin >> N >> M)) return 0;

    graf.assign(N + 1, vector<int>());
    graf_transpus.assign(N + 1, vector<int>());
    f.reserve(N);

    for (int i = 0; i < M; i++) {
        fin >> X >> Y;
        graf[X].push_back(Y);
        graf_transpus[Y].push_back(X);
    }

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

    vizitat.reset();

    for (auto it = f.rbegin(); it != f.rend(); ++it) {
        if (!vizitat[*it]) {
            nr_ctc++;
            ctc.emplace_back();
            dfs_transpusa(*it, ctc.back());
        }
    }

    fout << nr_ctc << "\n";

    for (int i = 0; i < nr_ctc; i++) {
        for (int nod : ctc[i]) {
            fout << nod << " ";
        }
        fout << "\n";
    }

    return 0;
}