Planets and Kingdoms

#include <bits/stdc++.h>
using namespace std;
 
/**
 * Descripción: Algoritmo de Kosaraju, DFS dos veces para generar
 * componentes fuertemente conexas en orden topológico. $a,b$
 * están en la misma componente si existen $a\to b$ y $b\to a$.
 * Tiempo: O(N+M)
 * Fuente: Wikipedia
 * Verificación: POI 8 peaceful commission
 */
 
struct SCC {
	int N;
	vector<vector<int>> adj, radj;
	vector<int> todo, comp, comps;
	vector<bool> vis;
	void init(int _N) {
		N = _N;
		adj.resize(N), radj.resize(N), comp = vector<int>(N, -1), vis.resize(N);
	}
	void ae(int x, int y) { adj[x].push_back(y), radj[y].push_back(x); }
	void dfs(int x) {
		vis[x] = 1;
		for (int y : adj[x])
			if (!vis[y]) dfs(y);
		todo.push_back(x);
	}
	void dfs2(int x, int v) {
		comp[x] = v;
		for (int y : radj[x])
			if (comp[y] == -1) dfs2(y, v);
	}
	void gen() {  // llena allComp
		for (int i = 0; i < N; i++)
			if (!vis[i]) dfs(i);
		reverse(begin(todo), end(todo));
		for (int x : todo)
			if (comp[x] == -1) { dfs2(x, x), comps.push_back(x); }
	}
};
 
int main() {
 
	int n, m, a, b;
	cin >> n >> m;
 
	SCC graph;
	graph.init(n);
	while (m--) {
		cin >> a >> b;
		graph.ae(--a, --b);
	}
	graph.gen();
 
	int ID[200000]{};
	int ids = 0;
	for (int i = 0; i < n; i++) {
		if (!ID[graph.comp[i]]) { ID[graph.comp[i]] = ++ids; }
	}
	cout << ids << '\n';
	for (int i = 0; i < n; i++) { cout << ID[graph.comp[i]] << " \n"[i == n - 1]; }
}

#include <bits/stdc++.h>
using namespace std;
 
/**
 * Descripción: Tarjan, DFS una sola vez para generar
 * componentes fuertemente conexas en orden topológico. $a,b$
 * están en la misma componente si existen $a\to b$ y $b\to a$.
 * Usa menos memoria que Kosaraju porque no guarda las aristas inversas.
 * Tiempo: O(N+M)
 * Fuente: KACTL
 * https://github.com/kth-competitive-programming/kactl/blob/master/content/graph/SCC.h
 * Verificación: https://cses.fi/problemset/task/1686/
 */
 
struct SCC {
	int N, ti = 0;
	vector<vector<int>> adj;
	vector<int> disc, comp, st, comps;
	void init(int _N) {
		N = _N;
		adj.resize(N), disc.resize(N), comp = vector<int>(N, -1);
	}
	void ae(int x, int y) { adj[x].push_back(y); }
	int dfs(int x) {
		int low = disc[x] = ++ti;
		st.push_back(x);  // disc[y] != 0 -> en la pila
		for (int y : adj[x])
			if (comp[y] == -1) low = min(low, disc[y] ?: dfs(y));
		if (low == disc[x]) {  // nueva SCC, desapilar hasta encontrar x
			comps.push_back(x);
			for (int y = -1; y != x;) comp[y = st.back()] = x, st.pop_back();
		}
		return low;
	}
	void gen() {
		for (int i = 0; i < N; i++)
			if (!disc[i]) dfs(i);
		reverse(begin(comps), end(comps));
	}
};
 
int main() {
 
	int n, m, a, b;
	cin >> n >> m;
 
	SCC graph;
	graph.init(n);
	while (m--) {
		cin >> a >> b;
		graph.ae(--a, --b);
	}
	graph.gen();
 
	int ID[200000]{};
	int ids = 0;
	for (int i = 0; i < n; i++) {
		if (!ID[graph.comp[i]]) { ID[graph.comp[i]] = ++ids; }
	}
	cout << ids << '\n';
	for (int i = 0; i < n; i++) { cout << ID[graph.comp[i]] << " \n"[i == n - 1]; }
}