Cod sursa(job #3372196)

Utilizator robertbaciuBaciu Vlad-Robert robertbaciu Data 2 noiembrie 2026 18:26:24
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#include <bitset>
#include <fstream>
#include <stack>
#include <vector>

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

int const NMAX = 100000;

std::vector<std::vector<int>> graph;
std::vector<std::vector<int>> graph_t;
std::bitset<NMAX + 1> visited;
std::stack<int> exits;

std::vector<int> node_ctc;
std::vector<std::vector<int>> ctcs;

void dfs(int curr) {
    visited[curr] = 1;

    for (int neigh : graph[curr]) {
        if (!visited[neigh]) {
            dfs(neigh);
        }
    }

    exits.push(curr);
}

void dfs_t(int curr, int ctc_no) {
    visited[curr] = 1;
    node_ctc[curr] = ctc_no;

    for (int neigh : graph_t[curr]) {
        if (!visited[neigh]) {
            dfs_t(neigh, ctc_no);
        }
    }

    exits.push(curr);
}

int main() {
    int n, m;
    fin >> n >> m;

    graph.resize(n + 1);
    graph_t.resize(n + 1);
    node_ctc.resize(n + 1);

    for (int i = 0; i < m; i++) {
        int a, b;
        fin >> a >> b;
        graph[a].push_back(b);
        graph_t[b].push_back(a);
    }

    dfs(1);

    visited.reset();

    int ctc_count = 0;
    while (!exits.empty()) {
        int curr = exits.top();
        exits.pop();

        if (!visited[curr]) {
            dfs_t(curr, ctc_count);
            ctc_count++;
        }
    }

    ctcs.resize(ctc_count);

    for (int i = 1; i <= n; i++) {
        ctcs[node_ctc[i]].push_back(i);
    }

    fout << ctc_count << '\n';
    for (auto &ctc : ctcs) {
        for (int node : ctc) {
            fout << node << ' ';
        }
        fout << '\n';
    }

    return 0;
}