Конденсация графа

def dfs1(h):
    used[h] = 1
    for a in G1[h]:
        if used[a] == 0:
            dfs1(a)
    R.append(h)

def dfs2(h):
    used[h] = 1
    P[h] = z
    for a in G2[h]:
        if P[a] == 0:
            dfs2(a)

n, m = map(int, input().split())
used = [0] * n
P = [0] * n
G1 = [[] for _ in range(n)]
G2 = [[] for _ in range(n)]

for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G1[a].append(b)
    G2[b].append(a)

R = []
for i in range(n):
    if used[i] == 0:
        dfs1(i)

R.reverse()
z = 1
for r in R:
    if P[r] == 0:
        dfs2(r)
        z += 1

print(z - 1)
print(*P, sep=" ")

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> G1, G2;
vector<bool> used;
vector<int> R, P;
int cnt = 1;

void dfs1(int v) {
    used[v] = true;
    for (int u : G1[v]) {
        if (!used[u]) {
            dfs1(u);
        }
    }
    R.push_back(v);
}

void dfs2(int v) {
    used[v] = true;
    P[v] = cnt;
    for (int u : G2[v]) {
        if (P[u] == 0) {
            dfs2(u);
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    
    G1.resize(n);
    G2.resize(n);
    used.resize(n, false);
    P.resize(n, 0);
    
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        G1[a].push_back(b);
        G2[b].push_back(a);
    }
    
    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            dfs1(i);
        }
    }
    
    reverse(R.begin(), R.end());
    
    for (int r : R) {
        if (P[r] == 0) {
            dfs2(r);
            cnt++;
        }
    }
    
    cout << cnt - 1 << "\n";
    for (int a : P) {
        cout << a << " ";
    }
    
    return 0;
}