Cod sursa(job #2789443)

Utilizator lucamLuca Mazilescu lucam Data 27 octombrie 2021 15:43:17
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <bits/stdc++.h>

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

constexpr int N = 1e5 + 1;

std::vector<int> g[N];
std::vector<int> gt[N];
int ts[N];
bool vis[N];
int tsi;

void tsort_dfs(int u) {
    vis[u] = true;
    for (auto v : g[u]) {
        if (!vis[v]) {
            tsort_dfs(v);
        }
    }
    ts[tsi--] = u;
}

bool dfst_print;
void dfst(int u) {
    vis[u] = true;
    if (dfst_print) {
        out << u << ' ';
    }
    for (auto v : gt[u]) {
        if (!vis[v]) {
            dfst(v);
        }
    }
}

int main() {
    int n, m;
    in >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v;
        in >> u >> v;
        g[u].push_back(v);
        gt[v].push_back(u);
    }
    tsi = n;
    for (int i = 1; i <= n; ++i) {
        if (!vis[i]) {
            tsort_dfs(i);
        }
    }
    std::fill(vis + 1, vis + n + 1, false);
    int cnt = 0;
    for (int i = 1; i <= n; ++i) {
        if (vis[ts[i]]) {
            continue;
        }
        ++cnt;
        dfst(ts[i]);
    }
    out << cnt << '\n';
    std::fill(vis + 1, vis + n + 1, false);
    dfst_print = true;
    for (int i = 1; i <= n; ++i) {
        if (vis[ts[i]]) {
            continue;
        }
        dfst(ts[i]);
        out << '\n';
    }
}