Cod sursa(job #3357972)

Utilizator TestLicenta123Test Test TestLicenta123 Data 13 iunie 2026 22:26:37
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

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

const int MAXN = 100001;
vector<int> G[MAXN], GT[MAXN], CTC[MAXN];
vector<int> order;
bool visited[MAXN];
int comp[MAXN];
int ctc_count = 0;

void DFS1(int u) {
    visited[u] = true;
    for (int v : G[u]) {
        if (!visited[v]) {
            DFS1(v);
        }
    }
    order.push_back(u);
}

void DFS2(int u, int comp_id) {
    visited[u] = true;
    comp[u] = comp_id;
    CTC[comp_id].push_back(u);
    for (int v : GT[u]) {
        if (!visited[v]) {
            DFS2(v, comp_id);
        }
    }
}

int main() {
    int N, M;
    fin >> N >> M;
    for (int i = 0; i < M; i++) {
        int x, y;
        fin >> x >> y;
        G[x].push_back(y);
        GT[y].push_back(x);
    }

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

    fill(visited, visited + N + 1, false);
    reverse(order.begin(), order.end());

    for (int u : order) {
        if (!visited[u]) {
            DFS2(u, ctc_count);
            ctc_count++;
        }
    }

    fout << ctc_count << "\n";
    for (int i = 0; i < ctc_count; i++) {
        for (int node : CTC[i]) {
            fout << node << " ";
        }
        fout << "\n";
    }

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