Конденсация (ор)графа(петли, кратные)

// Построим лес деревьев обхода, и отсортируем по убыванию времени выхода все вершины исходного графа
// Заметим, что ребра между вершинами двух разных компонент с.с. идут слева направо(относ индексов в отсорченном)
// Развернем все ребра и запустимся от самой "левой" вершины
// мы не попадем в другие компоненты, так как ребра между ними перевернулись
// мы найдем всю компоненту вершины, от которой запустились - v
// так как от всех этих вершин можно дойти до v по определению(в перевернутом получается можно от v до них)
// "удаляем" всю компоненту v и применяем те же рассуждения

const ll N = 2e5 + 100;
vector<ll> g[N][3], comp[N];
ll used[N], id[N];

void dfs(vector<ll>& orda, ll v, ll g_id = 0) {
    used[v] = 1;
    for (ll to : g[v][g_id])
        if (!used[to])
            dfs(orda, to, g_id);
    orda.push_back(v);
}

void $main()
{
    ll n, m; cin >> n >> m;
    for (ll i = 0; i < m; ++i) {
        ll v, u; cin >> v >> u;
        --v; --u;
        g[v][0].emplace_back(u);
        g[u][1].emplace_back(v);
    }

    vector<ll> orda;
    for (ll i = 0; i < n; ++i)
        if (!used[i])
            dfs(orda, i);
    fill(used, used + N, 0);

    ll top = 0;
    for (ll j = n-1; j >= 0; --j) {
        ll i = orda[j];
        if (!used[i]) {
            dfs(comp[top], i, 1);
            for (ll el : comp[top])
                id[el] = top;
            ++top;
        }
    }
    fill(used, used + N, 0);

    for (ll i = 0; i < n; ++i)
        for (ll to : g[i][2])
            g[id[i]][2].push_back(id[to]);

    vector<ll> meta_orda;
    for (ll i = 0; i < top; ++i)
        if (!used[i])
            dfs(meta_orda, i, 2);

    vector<ll> ans(n);
    ll it = 1;
    for (ll cid : meta_orda) {
        for (ll el : comp[cid])
            ans[el] = it;
        ++it;
    }
    cout << top << '\n';
    for (ll el : ans)
        cout << el << " ";
}