Skip to Content
CTRL K

Proving Equivalences

Explicación

Podemos modelar cada enunciado como un nodo de un grafo dirigido. Si el enunciado u implica el enunciado v, añadimos una arista dirigida u → v.

Para que todos los enunciados sean equivalentes, cada enunciado debe implicar a todos los demás. En términos de grafos, el grafo debe ser fuertemente conexo.

Comprimir las SCC

Podemos comprimir cada SCC en un solo nodo usando el algoritmo de Tarjan. Ahora sea k el número de SCC.

  • Si k = 1 el grafo ya es fuertemente conexo. La respuesta es 0.
  • Si no, hay que añadir aristas entre estas componentes

Hacerlas conexas

Una componente con:

  • grado de entrada 0 no se puede alcanzar desde las demás.
  • grado de salida 0 no puede alcanzar a las demás.

Sean

  • in0 = número de componentes con grado de entrada 0
  • out0 = número de componentes con grado de salida 0

Para que el DAG quede fuertemente conexo, debemos arreglar todas esas componentes.

Cada arista añadida puede arreglar a lo sumo una entrada faltante y una salida faltante.

Por lo tanto, el número mínimo de aristas necesarias es:

max⁡(in0,out0) \max(\text{in}_0, \text{out}_0)

Implementación

Complejidad temporal: O(n+m)\mathcal{O}(n + m)

 
 
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define pb push_back
 
// BeginCodeSnip{Tarjan Solver template}
class TarjanSolver {
  private:
	vector<vector<int>> rev_adj;
	vector<int> post, comp;
	vector<bool> visited;
	int timer = 0, id = 0;
 
	void fill_post(int at) {
		visited[at] = true;
		for (int n : rev_adj[at])
			if (!visited[n]) fill_post(n);
		post[at] = timer++;
	}
 
	void find_comp(int at) {
		visited[at] = true;
		comp[at] = id;
		for (int n : adj[at])
			if (!visited[n]) find_comp(n);
	}
 
  public:
	const vector<vector<int>> &adj;
 
	TarjanSolver(const vector<vector<int>> &adj)
	    : adj(adj), rev_adj(adj.size()), post(adj.size()), comp(adj.size()),
	      visited(adj.size()) {
 
		vector<int> nodes(adj.size());
		for (int i = 0; i < adj.size(); i++) {
			nodes[i] = i;
			for (int v : adj[i]) rev_adj[v].pb(i);
		}
 
		for (int i = 0; i < adj.size(); i++)
			if (!visited[i]) fill_post(i);
 
		sort(nodes.begin(), nodes.end(),
		     [&](int a, int b) { return post[a] > post[b]; });
 
		visited.assign(adj.size(), false);
		for (int v : nodes)
			if (!visited[v]) {
				find_comp(v);
				id++;
			}
	}
 
	int comp_num() const { return id; }
	int get_comp(int n) const { return comp[n]; }
};
// EndCodeSnip
 
void solve() {
	int n, m;
	cin >> n >> m;
 
	vector<vector<int>> g(n);
	while (m--) {
		int u, v;
		cin >> u >> v;
		g[--u].pb(--v);
	}
 
	TarjanSolver scc(g);
	int k = scc.comp_num();
 
	if (k == 1) {
		cout << 0 << "\n";
		return;
	}
 
	// BeginCodeSnip{Getting in and out degrees}
	vector<int> in(k), out(k);
	int cu, cv;
	for (int u = 0; u < n; ++u)
		for (int v : g[u]) {
			cu = scc.get_comp(u);
			cv = scc.get_comp(v);
			if (cu != cv) out[cu]++, in[cv]++;
		}
	// EndCodeSnip
 
	int in0 = 0, out0 = 0;
	for (int i = 0; i < k; ++i) {
		if (in[i] == 0) in0++;
		if (out[i] == 0) out0++;
	}
 
	cout << max(in0, out0) << "\n";
}
 
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
 
	int t;
	cin >> t;
	while (t--) solve();
}
Fundamentos