New Flight Routes

Explicación

Primero descompongamos el grafo en muchas SCC y construyamos el DAG correspondiente con las SCC como vértices. El problema se reduce a: ¿cuántas aristas hay que añadir en el DAG para que el DAG quede fuertemente conexo?

A partir de ahora solo consideramos el DAG. Un nodo es una fuente (source) si no tiene conexiones de entrada. Por otro lado, un nodo es un sumidero (sink) si no tiene conexiones de salida. Sea $S$ el conjunto de fuentes y $T$ el conjunto de sumideros. Solo deberíamos añadir aristas que vayan de un sumidero a una fuente (en caso contrario, cualquier otra arista que añadamos se puede reemplazar por aristas que van de un sumidero a una fuente y conectar más vértices).

Para cada vértice $u \in S$ , debemos hallar un vértice único $b \in T$ al que pueda llegar. El sumidero con el que se empareja puede ser arbitrario, pero solo debe viajar por vértices que aún no hayan sido visitados. Observemos que puede ocurrir que no se pueda emparejar cada fuente con un sumidero único. Por ahora, hemos creado muchos pares $(u_i, v_i)$ . Con estos pares, una construcción óptima es añadir aristas $v_i \rightarrow u_{i-1}$ para cada $i \geq 2$ y $v_1 \rightarrow u_k$ . De este modo, creamos un “anillo” donde podemos garantizar para todo vértice $u_i$ que también puede ser alcanzado por todos los vértices alcanzables desde $u_{i+1}$ . Esto es fuertemente conexo gracias a la arista $v_1 \rightarrow u_k$ . Si tenemos un par de vértices $(a, b)$ tal que $b$ era alcanzable desde $a$ pero $a$ no era alcanzable desde $b$ en el grafo original, ahora podemos partir de $b$ y recorrer el anillo hasta $a$ .

Sin embargo, puede haber fuentes y sumideros que no se emparejaron al inicio. Podemos conectar cada sumidero con una fuente única mediante una arista para que sus componentes queden fuertemente conexas. Para las fuentes o sumideros que aún queden, basta conectarlos al grafo nuevo añadiendo una arista. Observemos que, tanto si conectamos una fuente como un sumidero al grafo principal, la conexión se propaga al resto de los vértices de sus SCC.

Así, el número mínimo de aristas que debemos añadir es $\max(|S|,|T|)$ . Como ejercicio, demostrar por qué es óptimo.

Implementación

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

C++


#include <bits/stdc++.h>
using namespace std;
 
struct SCC {
	vector<vector<int>> adj, c_adj, r_adj;
	vector<int> c, v, ord;
 
	SCC(vector<vector<int>> _adj) : adj(_adj) {}
 
	void dfs(int i) {
		v[i] = 1;
		for (int j : adj[i])
			if (!v[j]) dfs(j);
		ord.push_back(i);
	}
 
	void partition(int i, int t) {
		v[i] = 1, c[i] = t;
		for (int j : r_adj[i])
			if (!v[j]) partition(j, t);
	}
 
	// devuelve un vector de componentes c t.q. c[i] == c[j] sii i y j
	// están en la misma componente fuertemente conexa, corre en O(E).
	vector<int> components() {
		int n = adj.size(), t = 0;
		v.assign(n, 0), r_adj.resize(n);
		for (int i = 0; i < n; i++) {
			for (int j : adj[i]) r_adj[j].push_back(i);
			if (!v[i]) dfs(i);
		}
		v.assign(n, 0), c.assign(n, 0);
		for (int i = n - 1; i >= 0; i--)
			if (!v[ord[i]]) partition(ord[i], t++);
		return c;
	}
};
 
int main() {
	int n, m;
	cin >> n >> m;
	vector<vector<int>> adj(n);
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		--u;
		--v;
		adj[u].push_back(v);
	}
 
	SCC strong(adj);
	vector<int> comp = strong.components();
 
	int num_comps = *max_element(comp.begin(), comp.end()) + 1;
 
	// una sola componente fuertemente conexa feliz :D
	if (num_comps == 1) {
		cout << 0 << "\n";
		return 0;
	}
 
	vector<vector<int>> comp_adj(num_comps);  // DAG de SCC
	vector<int> any_in_comp(num_comps), in_deg(num_comps), out_deg(num_comps);
 
	// construir el DAG de SCC
	for (int i = 0; i < n; i++) {
		int cur_comp = comp[i];
		any_in_comp[cur_comp] = i;
 
		for (int j : adj[i]) {
			int next_comp = comp[j];
			if (cur_comp != next_comp) {
				comp_adj[cur_comp].push_back(next_comp);
				out_deg[cur_comp]++;
				in_deg[next_comp]++;
			}
		}
	}
 
	// fuente = sin conexiones de entrada
	// sumidero = sin conexiones de salida
	vector<int> sources, sinks;
	for (int c = 0; c < num_comps; c++) {
		if (!in_deg[c]) { sources.push_back(c); }
		if (!out_deg[c]) { sinks.push_back(c); }
	}
 
	vector<bool> vis(n);
 
	// para cada fuente, intentar emparejar un sumidero al que pueda llegar
	auto find_sink = [&](auto self, int node) -> int {
		vis[node] = true;
		// esto es un sumidero porque no hay salidas
		if (comp_adj[node].empty()) { return node; }
		for (int i : comp_adj[node]) {
			if (vis[i]) continue;
			int sink = self(self, i);
			// encontramos un sumidero
			if (sink != -1) return sink;
		}
		return -1;
	};
 
	vector<int> matched_sources, matched_sinks;
	vector<int> unmatched_sources, unmatched_sinks;
	for (int source : sources) {
		// intentar emparejar una arista de la fuente a un sumidero
		int sink = find_sink(find_sink, source);
		if (sink == -1) {
			unmatched_sources.push_back(source);
		} else {
			matched_sources.push_back(source);
			matched_sinks.push_back(sink);
		}
	}
	for (int sink : sinks) {
		if (!vis[sink]) { unmatched_sinks.push_back(sink); }
	}
 
	vector<pair<int, int>> ans;
 
	// formar un anillo con los emparejamientos existentes
	for (int i = 0; i < matched_sources.size(); i++) {
		ans.push_back(
		    {matched_sinks[i], matched_sources[(i + 1) % matched_sources.size()]});
	}
	while (!unmatched_sources.empty() && !unmatched_sinks.empty()) {
		ans.push_back({unmatched_sinks.back(), unmatched_sources.back()});
		unmatched_sinks.pop_back();
		unmatched_sources.pop_back();
	}
	// conectar el primer sumidero con las fuentes no emparejadas restantes
	while (!unmatched_sources.empty()) {
		ans.push_back({0, unmatched_sources.back()});
		unmatched_sources.pop_back();
	}
	// conectar la primera fuente con los sumideros no emparejados restantes
	while (!unmatched_sinks.empty()) {
		ans.push_back({unmatched_sinks.back(), 0});
		unmatched_sinks.pop_back();
	}
 
	cout << ans.size() << "\n";
	for (auto [u, v] : ans) {
		cout << any_in_comp[u] + 1 << " " << any_in_comp[v] + 1 << "\n";
	}
}