Reachable Pairs

Explicación

El problema nos pide hallar el número de pares de nodos que son alcanzables entre sí, así que basta con llevar la cuenta del tamaño de cada componente conexa. Si hay $k$ componentes conexas y la $i$ -ésima componente tiene tamaño $a_i$ , entonces el número de pares alcanzables es

\sum_{i=1}^{k}{\binom{a_i}{2}}

ya que dos nodos son alcanzables si y solo si pertenecen a la misma componente conexa. Para mantener los valores de $a_i$ , podemos usar un Union-Find / conjuntos disjuntos (DSU).

En cada instante $i$ , si $s_i = 0$ , entonces se quitan todas las aristas incidentes al nodo $i$ , lo que parte la componente del nodo $i$ en varias componentes. Si $s_i = 1$ , entonces el nodo $i$ se quita de su componente, pero se agregan aristas entre todos los pares de vecinos del nodo $i$ , impidiendo que la componente se parta. En lugar de agregar todas estas aristas extra, podemos simplemente “desactivar” el nodo $i$ , reduciendo el tamaño de su componente en $1$ , mientras mantenemos las aristas adyacentes a él. Esto funciona porque dos vecinos cualesquiera del nodo $i$ solo pueden desconectarse cuando uno de ellos se quita.

Como quitar aristas no es posible en un DSU, en su lugar simulamos el proceso al revés, empezando con el DSU del grafo final y agregando aristas y nodos a medida que vamos hacia atrás. Para crear este grafo final, ponemos en $0$ los tamaños de las componentes de los nodos donde $s_i = 1$ (todas las demás componentes deberían empezar con tamaño $1$ ). Luego, conectamos todas las aristas entre nodos $i$ y $j$ donde $s_i = s_j = 1$ . Ahora, procesamos cada $s_i$ al revés. Si $s_i = 1$ , entonces aumentamos el tamaño de la componente del nodo $i$ en $1$ . En caso contrario, si $s_i = 0$ , agregamos todas las aristas incidentes al nodo $i$ a nuestro DSU.

Para calcular la respuesta, podemos guardar una variable $ans$ (inicialmente igual a $0$ ). Cada vez que se enlazan dos componentes de tamaños $x$ e $y$ , sumamos $xy$ a $ans$ (ya que cada par de nodos con un nodo de cada una de las dos componentes ahora es alcanzable). Cada vez que el tamaño de una componente cambia de $x$ a $x+1$ , sumamos $x$ a $ans$ (ya que el nodo agregado crea $x$ pares alcanzables, uno con cada otro nodo de su componente).

Implementación

Complejidad temporal: $\mathcal{O}((N + M) \cdot \alpha(n))$

C++


#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
struct DSU {
	// s es el tamaño de la componente, p es el padre
	vector<int> p, s;
	DSU(int n) : p(n, -1), s(n, 1) {}
	int parent(int x) {
		if (p[x] == -1) return x;
		else return p[x] = parent(p[x]);
	}
	int &size(int x) { return s[parent(x)]; }
	bool link(int x, int y) {
		x = parent(x), y = parent(y);
		if (x == y) return false;
		if (size(x) < size(y)) swap(x, y);
		s[x] += s[y];
		p[y] = x;
		return true;
	}
};
 
ll xchoose2(ll x) { return x * (x - 1) / 2; }
 
void solve() {
	int n, m;
	string s;
	cin >> n >> m >> s;
	vector<vector<int>> adj(n);
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
 
	DSU dsu(n);
	for (int i = 0; i < n; i++) {
		if (s[i] == '1') {
			dsu.size(i) = 0;
			for (int j : adj[i]) {
				if (s[j] == '1') { dsu.link(i, j); }
			}
		}
	}
 
	ll pairs = 0;
	vector<ll> ans;
	for (int i = n - 1; i >= 0; i--) {
		if (s[i] == '1') {
			pairs += dsu.size(i);
			dsu.size(i)++;
		} else {
			for (int j : adj[i]) {
				if (j < i && s[j] == '0') continue;
				if (dsu.parent(i) == dsu.parent(j)) continue;
				pairs += (ll)dsu.size(i) * dsu.size(j);
				dsu.link(i, j);
			}
		}
		ans.push_back(pairs);
	}
 
	reverse(ans.begin(), ans.end());
	for (auto i : ans) cout << i << '\n';
}
 
signed main() {
	cin.tie(0)->sync_with_stdio(0);
	solve();
}