Duathlon

Resumen

Partimos el grafo en sus componentes biconexas. Luego usamos conteo complementario y restamos el número de triples malos del total.

Intuición

En lugar de hallar el número de triples buenos, hallamos el número de triples malos y lo restamos del número de todos los triples. Esto se llama conteo complementario (complementary counting) y es útil en muchos problemas de conteo.

¿Qué hace malo a un triple? Un triple $(S, C, F)$ es malo si los caminos de $S$ a $C$ y de $C$ a $F$ pasan ambos por algún cuello de botella.

Esto sugiere que la solución involucrará puntos de articulación. Como este problema trata de alcanzabilidad, probablemente usemos también componentes biconexas.

Partir en BCCs

Imaginemos un segundo grafo donde:

• Cada componente biconexa también es un nodo.
• Cada nodo del grafo original tiene una arista hacia todas las componentes biconexas de las que forma parte.
• No hay otras aristas.

Observemos que este grafo es un árbol: si hay un ciclo, entonces las componentes biconexas que forman parte de ese ciclo forman una componente biconexa más grande por definición.

Contar los triples malos

Consideremos algún punto de articulación $P$ que forma parte de alguna BCC $B$.

Si quitamos $P$ del grafo, nos quedan el árbol más pequeño que contiene $B$ y varios otros árboles más pequeños.

Si $S$ y $F$ están ambos en el mismo árbol pequeño que no contiene $B$, entonces $C$ no puede estar en el árbol pequeño que contiene $B$.

La suma de tales pares $(S, F)$ es entonces el número de triples malos que cada par $(B, P)$ aporta al total de triples malos.

Podemos hacer un DFS para contar estos pares.

Complejidad

Tiempo: $\mathcal{O}(N + M)$.

Memoria: $\mathcal{O}(N + M)$.

Implementación

#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;
 
ll n, m, N, ans, sz[200001];
vector<int> graph[100001], bcc_graph[200001], stck;
int low[100001], tin[100001], timer = 1, bccs = 1;
 
void dfs(int node, int parent = 0) {
	low[node] = tin[node] = timer++;
	stck.push_back(node);
	N++;
	for (int i : graph[node])
		if (i != parent) {
			if (tin[i]) low[node] = min(low[node], tin[i]);
			else {
				dfs(i, node);
				low[node] = min(low[node], low[i]);
				if (low[i] >= tin[node]) {
					bcc_graph[node].push_back(n + bccs);
					while (!bcc_graph[n + bccs].size() ||
					       bcc_graph[n + bccs].back() != i) {
						bcc_graph[n + bccs].push_back(stck.back());
						stck.pop_back();
					}
					bccs++;
				}
			}
		}
}
 
void dfs2(int node) {
	sz[node] = (node <= n);
	for (int i : bcc_graph[node]) {
		dfs2(i);
		sz[node] += sz[i];
		if (node > n) ans -= bcc_graph[node].size() * sz[i] * (sz[i] - 1);
	}
	if (node > n) ans -= bcc_graph[node].size() * (N - sz[node]) * (N - sz[node] - 1);
}
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	while (m--) {
		int u, v;
		cin >> u >> v;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}
	FOR(i, 1, n + 1) if (!tin[i]) {
		N = 0;
		dfs(i);
		ans += N * (N - 1) * (N - 2);
		dfs2(i);
	}
	cout << ans;
	return 0;
}