Reachable Nodes

Explicación

El enfoque naive sería crear un arreglo 2D de $N$ por $N$ que registre si el nodo $v$ se puede alcanzar desde el nodo $u$ . Sin embargo, eso claramente ocuparía demasiada memoria ( $2.5 \cdot 10^9$ bytes o $2500$ MB). Podemos optimizar esto usando bitsets. Usando un arreglo 2D de bitsets, la complejidad revisada se vuelve $\frac{2.5 \cdot 10^9}{32} \cdot 4 = 3.25 \cdot 10^8$ bytes o $312.5$ MB, que es mucho más eficiente.

Para hacer el cálculo real, simplemente hacemos un DFS y, para cada nodo que un hijo puede alcanzar, lo marcamos también para el padre.

Implementación

Complejidad temporal: $\mathcal{O}(\frac{N \cdot M}{32})$

C++


#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e4;
 
vector<int> graph[MAXN + 1];
bitset<MAXN + 1> can[MAXN + 1];
vector<bool> visited(MAXN + 1);
 
void dfs(int node) {
	visited[node] = true;
 
	// base case: node can reach itself
	can[node][node] = 1;
 
	for (int i : graph[node]) {
		if (!visited[i]) { dfs(i); }
 
		// activate all bits that are also in its child
		can[node] |= can[i];
	}
}
 
int main() {
	cin.tie(0)->sync_with_stdio(0);
	int n, m;
	cin >> n >> m;
 
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		graph[u].push_back(v);
	}
	for (int i = 1; i <= n; i++) {
		if (!visited[i]) { dfs(i); }
	}
	for (int i = 1; i <= n; i++) {
		// output the number of activated bits
		cout << can[i].count() << " ";
	}
}