FUN MEGA-CONDENSATOR

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <cstdio>
#include <cassert>
#include <list>
using namespace std;

typedef long long ll;
namespace Mlxa {
    #define eol '\n'
    #define read cin
    #define mp make_pair
    template <class A> inline   void print (A a)    { cout << a << ' '; }
    template <class A> inline   void println (A a){ cout << a << eol; }
    template <class A> inline   void err (A a)  { cerr << a << ' '; }
    template <class A> inline   void errln (A a)    { cerr << a << eol; }
    template <class A, class... B> inline   void println(A a, B... b) { print(a); println(b...); }
    template <class A, class... B> inline   void errln  (A a, B... b) { err(a); errln(b...); }

    #define all(x) begin(x), end(x)
    #ifdef AC
        #define add_log(...) errln(">>", __VA_ARGS__)
    #else
        #define add_log(...) (void(0))
    #endif
    #define fastIO cin.tie(nullptr), ios_base::sync_with_stdio(false);
    #define read_from(x) assert(freopen(x, "r", stdin))
    #define write_to(x) assert(freopen(x, "w", stdout))
    template <class I>
    ostream& operator << (ostream &out, pair<I, I> p) {
        I b(p.first), e(p.second);
        if (b == e) out << "{  }";
        else {
            out << "{ ";
            for (I i(b); i != e; ++ i) out << *i << ' ';
            out << "}";
        } return out;
    }

} using namespace Mlxa;

struct Graph {
    vector< set<ll> > E;
    vector< set<ll> > R;
    Graph() {}
    void resize (ll n) {
        E.assign(n + 1, set<ll>());
        R.assign(n + 1, set<ll>());
    }
    inline ll n () { return E.size() - 1; }
    inline set<ll> edges (ll v, bool rev=false)
    { if (rev) return R[v]; return E[v]; }

    inline void connect (ll a, ll b) {
        E[a].insert(b);
        R[b].insert(a);
    }
};

Graph g, res;

vector<char> used;
vector<ll> order, in;

void dfs (ll i) {
    used[i] = true;
    for (ll j : g.edges(i))
    if (not used[j]) {
        dfs(j);
    }
    order.push_back(i);
}


void start () {
    read_from("in.txt");
    ll n, m; read >> n >> m;
    add_log("|V| =", n, "|E| =", m);
    g.resize(n);
    for (ll a, b, i(0); i < m; ++ i) {
        read >> a >> b;
        g.connect(a, b);
    }
    used.assign(g.n() + 1, false);
    in.assign(g.n() + 1, -1);
    for (ll i(1); i <= g.n(); ++ i)
    if (not used[i]) dfs(i);

    reverse(all(order));
    println("      Top-sorted like this:");
    add_log(mp(all(order)));
}


vector<ll> component;


void write_c (ll i) {
    used[i] = true;
    component.push_back(i);
    for (ll j : g.edges(i, true))
    if (not used[j]) write_c(j);
}

void separate () {
    used.assign(g.n() + 1, false);
    ll cnt(0);
    for (ll i : order)
    if (not used[i]) {
        write_c(i);
        add_log("Component @", ++ cnt, ":\t", mp(all(component)));
        for (ll v : component) in[v] = cnt;
        component.clear();
    } res.resize(cnt);
}

void condensate () {
    for (ll v(1); v <= g.n(); ++ v)
    for (ll u : g.edges(v))
    if (in[v] != in[u])
        res.connect(in[v], in[u]);

    for (ll C(1); C <= res.n(); ++ C) {
        auto tmp = res.edges(C);
        add_log("@", C, ":   ", mp(all(tmp)));
    }
}

int main () {
    println("-----Let's condensate it-----");
    start();

    println("------------------------------");
    println("     Separated components:");
    separate();

    println("------------------------------");
    println("     Graph condensation:");
    condensate();

    println("------------------------------");
    return 0;
}