Cod sursa(job #3259815)

Utilizator alexdumitruAlexandru Dumitru alexdumitru Data 27 noiembrie 2024 21:35:47
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

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

const int MAX_N = 100000;

int n, m;
std::vector<int> g[MAX_N + 1];
std::vector<int> rev_g[MAX_N + 1];
bool vis[MAX_N + 1];

void read() {
    fin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        fin >> u >> v;
        g[u].push_back(v);
        rev_g[v].push_back(u);
    }
}

std::stack<int> stk;

void dfs1(int node) {
    vis[node] = true;

    for (int to : g[node])
        if (!vis[to])
            dfs1(to);

    stk.push(node);
}

std::vector<int> comp;
std::vector<std::vector<int>> ans;


void dfs2(int node) {
    vis[node] = true;
    for (int to : rev_g[node])
        if (!vis[to])
            dfs2(to);
    comp.push_back(node);
}

void solve() {
    for (int i = 1; i <= n; i++)
        if (!vis[i])
            dfs1(i);
    for (int i = 1; i <= n; i++)
        vis[i] = false;
    while (!stk.empty()) {
        int node = stk.top();
        stk.pop();
        if (vis[node])
            continue;
        comp.clear();
        dfs2(node);
        ans.push_back(comp);
    }

    fout << ans.size() << '\n';

    for (const auto & v : ans) {
        for (const auto & x : v)
            fout << x << ' ';
        fout << '\n';
    }
}

int main() {
    read();
    solve();
    return 0;
}