Críticos

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	CSES	★ Critical Cities	Difícil		en el módulo

Recursos
Fuente	Recurso	Notas
Princeton	Dominator slides	¡Hechas por el creador del algoritmo mismo!
Wiki	Dominator	Definición de Wikipedia
Blog	Dominator Tree
Blog	Visualizing Dominators

Enfoque inicial

Estos nodos críticos de los que habla el problema se conocen comúnmente como dominadores. Definamos $\texttt{dom}(u)$ como el conjunto de nodos que dominan al nodo $u$ .

El dominador del nodo de partida es él mismo, y el conjunto de dominadores de cualquier otro nodo $u$ es la intersección del conjunto de dominadores de todos los ancestros $p$ del nodo $u$ .

\texttt{dom}(u)= \begin{cases} u\quad\text{ if } u \text{ is the starting point} \\ {u}\cup \left(\bigcap_{p \in \texttt{ancestor}(u)} \texttt{dom}(p)\right)\quad\text{otherwise} \end{cases}

Implementación

El siguiente código usa la recurrencia de arriba. Sin embargo, es demasiado lento y usa demasiada memoria. ¡Intentaremos optimizar esto a continuación!

Complejidad temporal: $\mathcal{O}(N^2)$ .

C++


#include <bitset>
#include <iostream>
#include <vector>
 
using std::bitset;
using std::cout;
using std::endl;
using std::vector;
 
const int MAX_N = 1e5;
 
int main() {
	int city_num;
	int flight_num;
	std::cin >> city_num >> flight_num;
	vector<vector<int>> rev_adj(city_num);
	for (int f = 0; f < flight_num; f++) {
		int a, b;
		std::cin >> a >> b;
		// notice that we need the edges in reverse
		rev_adj[--b].push_back(--a);
	}
 
	vector<bitset<MAX_N>> dom(city_num);
	dom[0].set(0);  // the dominator of the starting node is itself
	for (int c = 1; c < city_num; c++) { dom[c].set(); }
 
	bool changed;
	// iteratively update the dom sets of each node
	do {
		changed = false;
 
		// make a new vector where the updated doms reside
		vector<bitset<MAX_N>> new_dom(city_num);
		new_dom[0].set(0);
		for (int c = 1; c < city_num; c++) {
			bitset<MAX_N> updated = bitset<MAX_N>().set();
			for (int prev : rev_adj[c]) { updated &= dom[prev]; }
			updated.set(c);
 
			if (updated != dom[c]) { changed = true; }
			new_dom[c] = updated;
		}
 
		dom = new_dom;
	} while (changed);
 
	vector<int> critical;
	for (int c = 0; c < city_num; c++) {
		if (dom[city_num - 1][c]) { critical.push_back(c); }
	}
 
	cout << critical.size() << '\n';
	for (int i = 0; i < critical.size(); i++) {
		cout << critical[i] + 1 << " \n"[i == critical.size() - 1];
	}
}

Optimizar con árboles

En este enfoque, vamos a construir el árbol de dominadores del grafo.

Antes de discutir esto, definamos algunos términos que usaremos a lo largo de este módulo:

Un nodo $u$ domina estrictamente a otro nodo $v$ si $u$ domina a $v$ y $u \ne v$ .
Sea el dominador inmediato de $u$ , o $\texttt{idom}(u)$ , el único nodo $v$ tal que domina estrictamente al nodo $u$ y todo otro dominador del nodo $u$ domina estrictamente al nodo $v$ .
Sea $e(u)$ el tiempo de entrada en el nodo $u$ haciendo un tour de Euler.
Sea el semi-dominador de $u$ , o $\texttt{sdom}(u)$ , un $v$ tal que hay un camino de $v$ a $u$ y $e(i) \ge e(u)$ para cada nodo intermedio $i$ a lo largo del camino de $u$ a $v$ , excluyendo los extremos. Si hay múltiples nodos que cumplen este requisito, tomamos el nodo $v$ con el $e(v)$ más pequeño.
Sea el dominador relativo de $u$ , o $\texttt{rdom}(u)$ , el vértice $x \ne \texttt{sdom}(u)$ en el camino de $\texttt{sdom}(u)$ a $u$ en el árbol del tour de Euler con el número de nodo sdom más bajo. A diferencia del sdom, los empates en esta función se pueden romper de forma arbitraria.

Un árbol de dominadores es un árbol donde los hijos de cada nodo son aquellos nodos que domina inmediatamente. El nodo de partida es la raíz del árbol.

Dada esta definición, podemos ver que si un nodo domina a otro, entonces el primero es un ancestro del segundo en el árbol de dominadores. Así, la respuesta al problema de CSES es el conjunto de todos los nodos que yacen en el camino de la raíz al nodo $n$ en el árbol.

El siguiente grafo muestra el sdom de cada nodo. Las aristas de color pleno representan las aristas que forman parte del árbol DFS.

Graph2

Propiedades importantes

Las demostraciones de estas propiedades están más adelante en el módulo. Para todas estas propiedades, sea $u$ un nodo que no es el nodo de partida.

$\texttt{sdom}(u)$ es un ancestro propio de $u$ en el árbol DFS.
Si $\texttt{rdom}(u)=u$ , entonces $\texttt{idom}(u)=\texttt{sdom}(u)$ .
Si no, entonces $\texttt{idom}(u)=\texttt{idom}(\texttt{rdom}(u))$

Visión general del algoritmo

Antes de entrar en los detalles, aquí hay un esquema breve de cómo exactamente vamos a construir este árbol de dominadores.

Calcular el sdom de cada nodo excepto el de partida.
Calcular el rdom de cada nodo excepto el de partida.
Visitar todos los vértices en el árbol DFS y calcular su dominador inmediato usando la segunda y tercera propiedades listadas arriba. Observar que por cómo definimos el rdom de un nodo, un recorrido en preorden siempre visitará el rdom de un nodo antes que el nodo mismo si los dos no son iguales.

El primer y segundo pasos son terriblemente vagos: ¡aclaremos eso ahora!

Calcular $\texttt{sdom}$

Podemos calcular $\texttt{sdom}(u)$ como el nodo mínimo en la intersección de los siguientes grupos:

Todos los nodos $y$ tales que hay una arista de $y$ a $u$ y $e(y) \le e(u)$ .
Todos los valores de $\texttt{sdom}(x)$ donde $x$ es cualquier nodo tal que hay una arista de $u$ a $x$ y $e(x) > e(u)$ . Para ser más precisos matemáticamente, podemos definir este grupo como $\{\texttt{sdom}(x)\ |\ (u, x) \in E\text{ and }e(x)>e(u)\}$

La demostración de por qué esto funciona está fuera del alcance de este módulo.

Implementar $\texttt{sdom}$

Primero hacemos un recorrido DFS en preorden del grafo desde el nodo fuente y rastrearemos todos los tiempos de entrada de los nodos.

Luego, calculamos el sdom de todos los nodos aplicando la fórmula mencionada en la sección anterior. Para hacer esto, iteramos sobre el recorrido en orden inverso y mantenemos los nodos que hemos recorrido en un DSU.

Sin embargo, el DSU que usamos para este algoritmo va a ser un poco distinto. Unimos nodos de forma usual, pero la función find difiere.

Digamos que $x$ es la raíz de la componente sobre la que llamamos find. Si el nodo sobre el que llamamos find resulta ser x, entonces devolvemos x como de costumbre. Sin embargo, si es algún otro nodo, entonces devolvemos un nodo con el sdom mínimo que yace en el camino de $u$ a $x$ .

Para procesar el nodo $u$ iteramos sobre todos los nodos $v$ que tienen una arista dirigida hacia él. Si $v$ viene antes que $u$ en el recorrido en preorden, entonces $v$ es un ancestro de $u$ y no habría sido procesado hasta ahora. En ese caso, find(v) devolvería $v$ mismo.

Si no, entonces find(v) devolvería un nodo $x$ que yace en el camino de $v$ a la raíz en su componente DSU con el sdom más pequeño.

Si esta explicación todavía resulta un poco confusa, hay pseudocódigo en la diapositiva 33 de las diapositivas de Princeton dadas al comienzo de este módulo.

Calcular $\texttt{rdom}$

El rdom de un nodo es el nodo con el sdom que viene más temprano en el recorrido. Como esto se reduce a hallar el mínimo de un valor a lo largo de un cierto camino en un árbol, podemos implementarlo usando una aumentación de binary jumping.

Implementación

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

C++


#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdint>
#include <functional>
#include <iostream>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
// BeginCodeSnip{Tree Class for rdom}
template <typename T> class Tree {
  private:
	const int root = 0;
	const vector<int> &parents;
	const vector<T> &vals;
	const int log2dist;
	vector<vector<int>> pow2ends;
	vector<vector<T>> pow2mins;
	vector<int> depth;
 
  public:
	Tree(const vector<int> &parents, const vector<T> &vals)
	    : parents(parents), vals(vals),
	      log2dist(std::ceil(std::log2(parents.size() + 1))),
	      pow2ends(parents.size(), vector<int>(log2dist + 1)),
	      pow2mins(parents.size(), vector<T>(log2dist + 1)) {
		assert(parents[root] == -1);
 
		vector<vector<int>> children(parents.size());
		for (int n = 0; n < parents.size(); n++) {
			if (parents[n] != -1) { children[parents[n]].push_back(n); }
		}
		depth = vector<int>(parents.size());
		vector<int> frontier{root};
		while (!frontier.empty()) {
			int curr = frontier.back();
			frontier.pop_back();
			for (int n : children[curr]) {
				depth[n] = depth[curr] + 1;
				frontier.push_back(n);
			}
		}
 
		for (int n = 0; n < parents.size(); n++) {
			pow2mins[n][0] = vals[n];
			pow2ends[n][0] = parents[n];
		}
		for (int p = 1; p <= log2dist; p++) {
			for (int n = 0; n < parents.size(); n++) {
				int halfway = pow2ends[n][p - 1];
				if (halfway == -1) {
					pow2ends[n][p] = -1;
					pow2mins[n][p] = pow2mins[n][p - 1];
				} else {
					pow2ends[n][p] = pow2ends[halfway][p - 1];
					pow2mins[n][p] =
					    std::min(pow2mins[n][p - 1], pow2mins[halfway][p - 1]);
				}
			}
		}
	}
 
	/**
	 * @return the min value on the path from the ancestor to its descendant,
	 *         not including the ancestor.
	 */
	T min_val(int ancestor, int desc) {
		int dist = depth[desc] - depth[ancestor];
		T ret = vals[desc];
		int at = desc;
		for (int pow = 0; pow <= log2dist; pow++) {
			if ((dist & (1 << pow)) != 0) {
				ret = std::min(ret, pow2mins[at][pow]);
				at = pow2ends[at][pow];
			}
		}
		assert(at == ancestor);
		return ret;
	}
};
// EndCodeSnip
 
int main() {
	int city_num;
	int flight_num;
	std::cin >> city_num >> flight_num;
	vector<vector<int>> adj(city_num);
	vector<vector<int>> rev_adj(city_num);
	for (int f = 0; f < flight_num; f++) {
		int a, b;
		std::cin >> a >> b;
		adj[--a].push_back(--b);
		rev_adj[b].push_back(a);
	}
 
	// Variables used for the Euler Tour
	vector<int> visit_order;
	// visit_time is initialized with INF so nodes that aren't reachable
	// during the DFS won't mess up our sdom calculation
	vector<int> visit_time(city_num, INT32_MAX);
	vector<int> visit_parent(city_num, -1);
	vector<bool> visited(city_num, false);
	std::function<void(int, int)> dfs;
	dfs = [&](int at, int prev) {
		if (visited[at]) { return; }
		visited[at] = true;
 
		visit_time[at] = visit_order.size();
		visit_order.push_back(at);
		visit_parent[at] = prev;
		for (int next : adj[at]) { dfs(next, at); }
	};
	dfs(0, -1);
 
	// We use a function-based interface instead of a class-based one due to
	// heavy reliance on previously calculated values
	vector<int> dsu_parent(city_num, -1);
	vector<int> dsu_min(city_num, INT32_MAX);
	std::function<int(int)> find;
	find = [&](int x) {
		if (dsu_parent[x] == -1) { return x; }
		if (dsu_parent[dsu_parent[x]] != -1) {
			int parent_res = find(dsu_parent[x]);
			if (visit_time[parent_res] < visit_time[dsu_min[x]]) {
				dsu_min[x] = parent_res;
			}
			dsu_parent[x] = dsu_parent[dsu_parent[x]];
		}
		assert(dsu_min[x] != INT32_MAX);
		return dsu_min[x];
	};
 
	vector<int> sdom(city_num, -1);
	for (int i = visit_order.size() - 1; i > 0; i--) {
		int c = visit_order[i];
		// Iterate over all nodes with a directed edge to c
		for (int from : rev_adj[c]) {
			int find_res = find(from);
			// Take the node with the earliest visit time in the traversal
			if (sdom[c] == -1 || visit_time[find_res] < visit_time[sdom[c]]) {
				sdom[c] = find_res;
			}
		}
 
		// Link c to its parent in the DFS tree
		dsu_parent[c] = visit_parent[c];
		dsu_min[c] = sdom[c];
	}
 
	// Initialize the values in the tree
	vector<std::pair<int, int>> sdom_times(city_num, {INT32_MAX, -1});
	for (int c : visit_order) {
		if (c != 0) {
			// The tree takes the minimum of these pairs, but what we
			// really want is the node itself- therefore, we store both
			sdom_times[c] = {visit_time[sdom[c]], c};
		}
	}
	Tree tree(visit_parent, sdom_times);
 
	vector<int> rdom(city_num, -1);
	for (int c : visit_order) {
		if (c != 0) {
			// Use the definition of the rdom
			rdom[c] = tree.min_val(sdom[c], c).second;
		}
	}
 
	// Use the properties previously given to compute the idom
	vector<int> idom(city_num, -1);
	for (int c : visit_order) {
		if (c != 0) { idom[c] = rdom[c] == c ? sdom[c] : idom[rdom[c]]; }
	}
 
	// Trace the idom tree from the finish node to the start node,
	// finding all dominators along the way
	vector<int> critical{0};
	int at = city_num - 1;
	while (at != 0) {
		critical.push_back(at);
		at = idom[at];
	}
 
	std::sort(critical.begin(), critical.end());
 
	cout << critical.size() << '\n';
	for (int i = 0; i < critical.size() - 1; i++) { cout << critical[i] + 1 << ' '; }
	cout << critical.back() + 1 << endl;
}

Ciclos

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	CF	★ The Meeting Place Cannot Be Changed 2	Difícil		en el módulo

Explicación

El problema pide hallar un nodo de intersección de todos los ciclos, si existe.

Primero, quitemos los nodos que no pertenecen a ningún ciclo. Para hacer esto, podemos quitar recursivamente los nodos sin ninguna arista saliente. Por “recursivamente” queremos decir que después de terminar con un nodo podemos revisar sus padres para ver si los padres tampoco tienen aristas salientes.

Ahora nuestro grafo es básicamente un montón de ciclos. Asumiendo que la intersección de todos los ciclos no es vacía, reducimos los ciclos nodo por nodo. El último nodo en pie es la intersección.

Implementación

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

C++


#include <functional>
#include <iostream>
#include <unordered_set>
#include <vector>
 
using namespace std;
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
 
	int n, m;
	cin >> n >> m;
 
	vector<unordered_set<int>> in(n), out(n);
	for (int i = 0; i < m; i++) {
		int x, y;
		cin >> x >> y;
		out[--x].insert(--y);
		in[y].insert(x);
	}
 
	// Recursively remove nodes without outgoing edges
	function<void(int)> dfs = [&](int node) {
		if (!out[node].empty()) { return; }
		for (int p : in[node]) {
			out[p].erase(node);
			dfs(p);
		}
		in[node].clear();
	};
	// Check for nodes with no outgoing edges
	for (int i = 0; i < n; i++) {
		if (out[i].empty()) { dfs(i); }
	}
 
	// Reduce cycles by popping out nodes
	vector<int> todo;
	vector<bool> seen(n);
	for (int i = 0; i < n; i++) {
		if ((int)out[i].size() == 1) {
			todo.push_back(i);
			seen[i] = true;
		}
	}
	while (!todo.empty()) {
		int node = todo.back();
		todo.pop_back();
 
		int next = *out[node].begin();
		if (node == next) { continue; }
 
		in[next].erase(node);
		in[next].insert(in[node].begin(), in[node].end());
		for (int p : in[node]) {
			out[p].erase(node);
			out[p].insert(next);
			if ((int)out[p].size() == 1 && !seen[p]) {
				todo.push_back(p);
				seen[p] = true;
			}
		}
 
		out[node].clear();
		in[node].clear();
	}
 
	// Get the last node standing.
	// If there are multiple nodes, then there is no intersection
	int ans = -1;
	for (int i = 0; i < n; i++) {
		if (!out[i].empty()) {
			if (ans == -1) {
				ans = i + 1;
			} else {
				ans = -1;
				break;
			}
		}
	}
 
	cout << ans << endl;
}

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	CF	★ Useful Roads	Difícil		—
	Kattis	★ Ski Resort	Difícil		—

Críticos

Enfoque inicial

Implementación

Optimizar con árboles

Propiedades importantes

Visión general del algoritmo

Calcular sdom\texttt{sdom}sdom

Implementar sdom\texttt{sdom}sdom

Calcular rdom\texttt{rdom}rdom

Implementación

Ciclos

Explicación

Implementación

Calcular $\texttt{sdom}$

Implementar $\texttt{sdom}$

Calcular $\texttt{rdom}$