Planets Queries II

En este problema, se nos da un grafo funcional y se nos piden $q$ consultas de la distancia mínima entre dos vértices $u$ y $v$ .

Estructura del grafo

Nótese que todos los grafos funcionales se pueden descomponer en un conjunto de “componentes”. Cada una de estas componentes consiste en muchos árboles dirigidos hacia la raíz, y un único ciclo compuesto por dichas raíces y algunos otros nodos.

Aquí hay un ejemplo de una posible “componente”. Los árboles están circulados en rojo:

Dado esto, esencialmente podemos descomponer cada consulta en tres casos:

Ambos en un árbol

Si tanto $u$ como $v$ están en un árbol, primero tenemos que obtener la distancia de cada nodo al ciclo. Esto se puede precalcular para todos los nodos con BFS.

En primer lugar, si la distancia de $v$ es mayor que la de $u$ , no podemos llegar a $v$ porque usar un teletransportador solo puede disminuir nuestra distancia al ciclo.

Pero si esta condición no se satisface, empezamos en $u$ y usamos los teletransportadores hasta que nuestra distancia al ciclo sea igual a la de $v$ . Si realmente terminamos en $v$ , entonces nuestra respuesta es la diferencia entre las distancias. En caso contrario, es imposible llegar a $v$ .

Para ver en qué planeta terminamos si nos teletransportamos $t$ veces, podemos usar binary jumping.

Ambos en un ciclo

Si ambos están en un ciclo, obtenemos el índice de $u$ y de $v$ en el ciclo. Llamemos a estos índices $u_i$ y $v_i$ respectivamente. Ahora, si $u_i \leq v_i$ , entonces nuestra respuesta es $v_i - u_i$ . Por otro lado, si $u_i > v_i$ , entonces nuestra respuesta es $\texttt{cycle\\_len} - (u_i - v_i)$ .

Uno en cada uno

Este caso es realmente dos casos, pero solo necesitamos considerar uno de ellos.

Si $u$ está en un ciclo pero $v$ está en un árbol, es imposible llegar a $v$ desde $u$ porque solo podemos ir de un árbol a un ciclo, no al revés.

Por otro lado, si $u$ es el que está en el árbol, obtenemos a qué nodo del ciclo se conecta el árbol de $u$ , que también es la raíz. Entonces esto se reduce a una versión del segundo caso: solo tenemos que sumar también la distancia de $u$ a la raíz.

Implementación

Complejidad temporal: $\mathcal{O}((n+q)\log n)$

C++Java


#include <cmath>
#include <iostream>
#include <map>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
int main() {
	int planet_num;
	int query_num;
	std::cin >> planet_num >> query_num;
	vector<int> next(planet_num);
	vector<vector<int>> before(planet_num);
	for (int p = 0; p < planet_num; p++) {
		std::cin >> next[p];
		next[p]--;
		before[next[p]].push_back(p);
	}
 
	/*
	 * -2 = We haven't even got to processing this planet yet.
	 * -1 = This node is part of a tree.
	 * >= 0: the ID of the cycle the planet belongs to.
	 */
	vector<int> cycle_id(planet_num, -2);
	// Each map, given a planet #, returns the index of that planet in the
	// cycle.
	vector<std::map<int, int>> cycles;
	for (int p = 0; p < planet_num; p++) {
		if (cycle_id[p] != -2) { continue; }
		vector<int> path{p};
		int at = p;
		while (cycle_id[next[at]] == -2) {
			at = next[at];
			cycle_id[at] = -3;  // Leave breadcrumbs for this iteration
			path.push_back(at);
		}
 
		std::map<int, int> cycle;
		bool in_cycle = false;
		for (int i : path) {
			in_cycle = in_cycle || i == next[at];
			if (in_cycle) { cycle[i] = cycle.size(); }
			cycle_id[i] = in_cycle ? cycles.size() : -1;
		}
		cycles.push_back(cycle);
	}
 
	/*
	 * Precalculate the distance from each planet to its cycle with BFS.
	 * (cyc_dist[p] = 0) if p is part of a cycle.
	 */
	vector<int> cyc_dist(planet_num);
	for (int p = 0; p < planet_num; p++) {
		// Check if this planet is part of a cycle.
		if (cycle_id[next[p]] == -1 || cycle_id[p] != -1) { continue; }
		cyc_dist[p] = 1;
		vector<int> stack(before[p]);
		while (!stack.empty()) {
			int curr = stack.back();
			stack.pop_back();
			cyc_dist[curr] = cyc_dist[next[curr]] + 1;
			stack.insert(stack.end(), before[curr].begin(), before[curr].end());
		}
	}
 
	// Initialize the binary jumping arrays.
	int log2 = std::ceil(std::log2(planet_num));
	vector<vector<int>> pow2_ends(planet_num, vector<int>(log2 + 1));
	for (int p = 0; p < planet_num; p++) { pow2_ends[p][0] = next[p]; }
	for (int i = 1; i <= log2; i++) {
		for (int p = 0; p < planet_num; p++) {
			pow2_ends[p][i] = pow2_ends[pow2_ends[p][i - 1]][i - 1];
		}
	}
 
	/*
	 * Given a starting planet & dist, returns the planet we end up at
	 * if we use the teleporter dist times.
	 */
	auto advance = [&](int pos, int dist) {
		for (int pow = log2; pow >= 0; pow--) {
			if ((dist & (1 << pow)) != 0) { pos = pow2_ends[pos][pow]; }
		}
		return pos;
	};
	for (int q = 0; q < query_num; q++) {
		int u, v;  // going from u to v
		std::cin >> u >> v;
		u--;
		v--;
		if (cycle_id[pow2_ends[u][log2]] != cycle_id[pow2_ends[v][log2]]) {
			cout << -1 << '\n';
			continue;
		}
		if (cycle_id[u] != -1 || cycle_id[v] != -1) {
			if (cycle_id[v] == -1 && cycle_id[u] != -1) {
				cout << -1 << '\n';
				continue;
			}
			// Handle the 2nd & 3rd cases at the same time.
			int dist = cyc_dist[u];
			int u_cyc = advance(u, cyc_dist[u]);  // The root of u's tree
 
			std::map<int, int> &cyc = cycles[cycle_id[u_cyc]];  // u and v's cycle
			int u_ind = cyc[u_cyc];
			int v_ind = cyc[v];
			int diff = u_ind <= v_ind ? v_ind - u_ind : cyc.size() - (u_ind - v_ind);
			cout << dist + diff << '\n';
		} else {
			if (cyc_dist[v] > cyc_dist[u]) {
				cout << -1 << '\n';
				continue;
			}
			int diff = cyc_dist[u] - cyc_dist[v];
			cout << (advance(u, diff) == v ? diff : -1) << '\n';
		}
	}
}


import java.io.*;
import java.util.StringTokenizer;
 
public class PlanetQueries2 {
	private static int MAX_HEIGHT = 20;
	private static int[][] binaryLifting;
	private static int[] arr;
	private static int[] len;
	private static boolean[] visited;
 
	public static void main(String[] args) {
		Kattio io = new Kattio();
		StringBuilder output = new StringBuilder();
		int n = io.nextInt();
		int q = io.nextInt();
		arr = new int[n + 1];
		binaryLifting = new int[n + 1][MAX_HEIGHT];
		len = new int[n + 1];
 
		for (int i = 1; i <= n; i++) { arr[i] = io.nextInt(); }
 
		// visited array ensures to cover more than one connected components
		visited = new boolean[n + 1];
		for (int i = 1; i <= n; i++) {
			if (!visited[i]) { dfs(i); }
		}
 
		for (int i = 0; i < q; i++) {
			int a = io.nextInt();
			int b = io.nextInt();
			// in case, a is in front of b
			int aa = jump(a, len[a]);
			int answer;
			if (jump(a, len[a] - len[b]) == b) {
				answer = len[a] - len[b];
			} else if (jump(aa, len[aa] - len[b]) == b) {
				answer = (len[aa] - len[b]) + len[a];
			} else {
				answer = -1;
			}
			output.append(answer).append("\n");
			/*
			 * in any of the edge cases, for example, (u,v) u being in cycle and
			 * v is in tree u will never be able to "jump" to v, and this is
			 * precisely being checked in the above if conditions.
			 */
		}
		io.println(output);
		io.close();
	}
 
	private static void dfs(int node) {
		/*
		 * while doing dfs, for each node, to ensure to covering
		 * more than one connected component
		 */
		if (visited[node]) { return; }
		visited[node] = true;
		dfs(arr[node]);
		/*
		 * head recursion is being used here, in order to start counting the
		 * height of the graph, from the left nodes of the tree (if one
		 * exists)
		 */
		binaryLifting[node][0] = arr[node];
		len[node] = len[binaryLifting[node][0]] + 1;
		for (int level = 1; level < MAX_HEIGHT; level++) {
			binaryLifting[node][level] =
			    binaryLifting[binaryLifting[node][level - 1]][level - 1];
		}
	}
 
	private static int jump(int a, int dist) {
		if (dist < 0) return -1;
		int level = 0;
		while (dist != 0) {
			if ((dist & 1) == 1) { a = binaryLifting[a][level]; }
			level++;
			dist = dist / 2;
		}
		return a;
	}
 
	// CodeSnip{Kattio}
}