Cod sursa(job #2384991)

Utilizator MateiTrandafirMatei Trandafir MateiTrandafir Data 21 martie 2019 13:45:25
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#include <fstream>

constexpr int MAX_N = 100001, MAX_M = 200001;

int n, m;
int start[MAX_N], next[MAX_M], at[MAX_M], count;
int rStart[MAX_N], rNext[MAX_M], rAt[MAX_M], rCount;
bool vis[MAX_N], rVis[MAX_N];
int t[MAX_N], tCount;
int res[MAX_N], nums[MAX_N], num, resCount;

inline void add(int from, int to) {
    ++count;
    at[count] = to;
    next[count] = start[from];
    start[from] = count;
}

inline void rAdd(int from, int to) {
    ++rCount;
    rAt[rCount] = to;
    rNext[rCount] = rStart[from];
    rStart[from] = rCount;
}

inline void tSort(int x) {
    vis[x] = true;
    for (int p = start[x]; p != 0; p = next[p]) if (!vis[at[p]]) tSort(at[p]);
    t[++tCount] = x;
}

inline void ctc(int x) {
    rVis[x] = true;
    res[++resCount] = x;
    nums[resCount] = num;
    for (int p = rStart[x]; p != 0; p = rNext[p]) if (!rVis[rAt[p]]) ctc(rAt[p]);
}

int main() {
    std::ifstream in("ctc.in");
    std::ofstream out("ctc.out");
    int i, x, y;
    in >> n >> m;
    for (i = 0; i < m; ++i) {
        in >> x >> y;
        add(x, y);
        rAdd(y, x);
    }
    for (i = 1; i <= n; ++i) if (!vis[i]) tSort(i);
    for (i = n; i >= 1; --i) {
        if (!rVis[t[i]]) {
            ++num;
            ctc(t[i]);
        }
    }
    out << num << '\n';
    int oldNum = nums[1];
    for (i = 1; i <= n; ++i) {
        if (oldNum != nums[i]) {
            out << '\n';
            oldNum = nums[i];
        }
        out << res[i] << ' ';
    }
    return 0;
}