Skip to Content
CTRL K

2018 - Bike Paths

Explicación

Observemos que grupos de intersecciones pueden formar componentes fuertemente conexas. Por lo tanto, tratamos cada componente como un nodo con valor inicial igual al tamaño de la componente. Como las componentes fuertemente conexas resultantes comp\texttt{comp} forman un grafo dirigido acíclico (específicamente un árbol, por la “justicia” del enunciado), procesamos las aristas ee en orden topológico inverso cc con la siguiente relación, donde dp[i]\texttt{dp}[i] es el número de intersecciones que se pueden alcanzar desde la componente ii:

dp[comp[e]]=dp[comp[e]]+∑e∈radj[c]dp[comp[c]]:comp[c]≠comp[e] \texttt{dp}[\texttt{comp}[e]] = \texttt{dp}[\texttt{comp}[e]] +\sum_{e \in \texttt{radj}[c]} \texttt{dp}[\texttt{{comp}}[c]] : \texttt{comp}[c] \neq \texttt{comp}[e]

La respuesta final para la intersección ii es dp[comp[i]]−1\texttt{dp}[\texttt{comp}[i]] - 1, ya que excluimos la intersección de partida de la respuesta.

Implementación

Complejidad temporal: O(N+M)\mathcal{O}(N + M)

// CodeSnip{Benq Template}
 
/**
 * Description: Kosaraju's Algorithm, DFS twice to generate
 * strongly connected components in topological order. $a,b$
 * in same component if both $a\to b$ and $b\to a$ exist.
 * Time: O(N+M)
 * Source: Wikipedia
 * Verification: POI 8 peaceful commission
 */
struct SCC {
	int N;
	vector<vi> adj, radj;
	vi todo, comp, comps;
	vector<bool> vis;
	void init(int _N) {
		N = _N;
		adj.rsz(N), radj.rsz(N), comp = vi(N, -1), vis.rsz(N);
	}
	void ae(int x, int y) { adj[x].pb(y), radj[y].pb(x); }
	void dfs(int x) {
		vis[x] = 1;
		each(y, adj[x]) if (!vis[y]) dfs(y);
		todo.pb(x);
	}
	void dfs2(int x, int v) {
		comp[x] = v;
		each(y, radj[x]) if (comp[y] == -1) dfs2(y, v);
	}
	void gen() {  // fills allComp
		F0R(i, N) if (!vis[i]) dfs(i);
		reverse(all(todo));
		each(x, todo) if (comp[x] == -1) dfs2(x, x), comps.pb(x);
	}
};
 
int N, M;
 
int dp[100001];
 
int main() {
	setIO();
 
	re(N, M);
	SCC scc;
	scc.init(N);
	F0R(i, M) {
		int1(a, b);
		scc.ae(a, b);
	}
 
	scc.gen();
 
	F0R(i, N) { dp[scc.comp[i]]++; }  // component size
	reverse(all(scc.todo));
 
	each(c, scc.todo) {
		// use reverse edges since we process in reverse order
		each(e, scc.radj[c]) {
			if (scc.comp[c] != scc.comp[e]) { dp[scc.comp[e]] += dp[scc.comp[c]]; }
		}
	}
 
	F0R(i, N) { ps(dp[scc.comp[i]] - 1); }
}
Fundamentos