Isla Solitaria#9044

Isla Solitaria (Editorial)

Según el enunciado del problema, una vez que abandonas una isla nunca puedes regresar a ella. Por lo tanto, el grafo cuyos vértices son las islas y cuyas aristas son los puentes es un grafo acíclico dirigido. Solo puedes quedarte atascado en una isla $v$ sin puentes salientes, es decir, en un vértice sin salida con grado de salida cero: $O u t D e g r ee [v] = 0$ OutDegree[v] = 0.

Sea $p r o b [v]$ prob[v] la probabilidad de que durante el recorrido lleguemos al vértice $v$ . Para el vértice inicial $p r o b [r] = 1$ prob[r] = 1; para todos los demás vértices inicialmente $p r o b [v] = 0$ prob[v] = 0. Dado que el grafo no contiene ciclos, cada vértice puede visitarse como máximo una vez.

Supongamos que del vértice $u$ salen $O u t D e g r ee [u]$ OutDegree[u] aristas. Estando en $u$ , elegimos una de ellas de manera uniformemente aleatoria, de modo que nos movemos por cada arista $u \to v$ u \to v con probabilidad $p r o b [u] / O u t D e g r ee [u]$ prob[u] / OutDegree[u]. Al vértice $v$ solo se puede llegar desde sus predecesores directos. Por lo tanto, $p r o b [v]$ prob[v] es igual a la suma de las contribuciones de todas las aristas $u \to v$ u \to v que entran en $v$ :

p r o b [v] = u \to v \sum p r o b [u] / O u t D e g r ee [u]

prob[v] = \sum_{u \to v} prob[u] / OutDegree[u]

El valor $p r o b [v]$ prob[v] solo puede calcularse cuando las probabilidades de todos sus predecesores son definitivas. Este es exactamente el orden de procesamiento que proporciona un orden topológico: cada vértice aparece después de todos los vértices desde los cuales llegan aristas hacia él. Por lo tanto, construimos el orden topológico usando el algoritmo de Kahn y, al mismo tiempo, "empujamos" las probabilidades a lo largo de las aristas.

El algoritmo es el siguiente:

para cada vértice $v$ , calcular su grado de entrada $I n D e g r ee [v]$ InDegree[v] y grado de salida $O u t D e g r ee [v]$ OutDegree[v];
colocar en la cola todos los vértices con grado de entrada cero y establecer $p r o b [r] = 1$ prob[r] = 1;
mientras la cola no esté vacía, extraer un vértice $v$ de ella. En este momento, todos sus predecesores ya han sido procesados, por lo que el valor $p r o b [v]$ prob[v] es definitivo. Para cada arista $v \to t o$ v \to to, sumar $p r o b [v] / O u t D e g r ee [v]$ prob[v] / OutDegree[v] a $p r o b [t o]$ prob[to] y disminuir $I n D e g r ee [t o]$ InDegree[to] en $1$ . Si el grado de entrada del vértice $t o$ se vuelve cero, colocarlo en la cola.

Inicialmente, la cola contiene todos los vértices con grado de entrada cero, no solo el vértice inicial. Los vértices inalcanzables desde $r$ también se procesan, pero su probabilidad permanece en cero y no afecta la respuesta.

Encontrar la respuesta. Entre los vértices sin salida, encontrar la probabilidad máxima $m x$ . Luego imprimir, en orden creciente, los índices de todos los vértices sin salida $v$ tales que $∣ p r o b [v] - m x ∣ \leq 1 0^{- 9}$ |prob[v] - mx| \le 10^{-9}. La comparación con tolerancia es necesaria porque las probabilidades se calculan con números de punto flotante con errores de redondeo.

Complejidad. Cada vértice se coloca y se extrae de la cola exactamente una vez, y cada arista se examina una vez. El tiempo de ejecución del algoritmo es $O (n + m)$ O(n + m).

Ejemplo

Simulemos el algoritmo sobre el grafo del ejemplo. Junto a cada vértice se muestra la probabilidad $p r o b [v]$ prob[v] de alcanzarlo. Los vértices procesados están sombreados en gris, las aristas a lo largo de las cuales se distribuye la probabilidad en el paso actual están resaltadas en azul, y las aristas ya examinadas se dibujan con línea discontinua.

Inicialmente (figura izquierda) $p r o b [1] = 1$ prob[1] = 1, y las probabilidades de todos los demás vértices son $0$ . El vértice $1$ es el único vértice con grado de entrada cero, por lo que es el primero en extraerse de la cola.

Del vértice $1$ salen cuatro aristas, por lo que la probabilidad $p r o b [1] = 1$ prob[1] = 1 se divide equitativamente entre los vértices $2, 3, 4$ y $5$ : cada uno de ellos recibe $1/4 = 0.25$ 1 / 4 = 0.25 (figura derecha). Tras eliminar las aristas que salen del vértice $1$ , los grados de entrada de los vértices $2$ y $3$ se vuelven cero, y se colocan en la cola.

A continuación se procesa el vértice $2$ . De él salen dos aristas, por lo que se suma $p r o b [2] /2 = 0.25/2 = 0.125$ prob[2] / 2 = 0.25 / 2 = 0.125 a $p r o b [4]$ y $p r o b [5]$ . Obtenemos $p r o b [4] = p r o b [5] = 0.375$ prob[4] = prob[5] = 0.375 (figura inferior izquierda). El grado de entrada del vértice $5$ se vuelve cero, y se coloca en la cola.

A continuación se procesa el vértice $3$ . De él sale una única arista $3 \to 4$ 3 \to 4, por lo que $p r o b [4]$ aumenta en $p r o b [3] /1 = 0.25$ prob[3] / 1 = 0.25 y pasa a ser $0.625$ (figura inferior derecha). Ahora el vértice $4$ también se coloca en la cola.

Los vértices $5$ y $4$ no tienen aristas salientes, por lo que procesarlos no cambia ninguna probabilidad. El orden topológico resultante es $1, 2, 3, 5, 4$ 1, 2, 3, 5, 4.

Los vértices sin salida son $4$ y $5$ , con probabilidades $0.625$ y $0.375$ respectivamente. Su suma es igual a $1$ : tenemos la certeza de quedarnos atascados en algún lugar. La probabilidad máxima se alcanza en el único vértice $4$ , que es la respuesta.

Implementación del algoritmo

Declarar la constante $E P S$ — la tolerancia para comparar números de punto flotante.

#define EPS 1e-9

Almacenar el grafo de entrada como una lista de adyacencia $g$ . Almacenar los grados de entrada y de salida de los vértices en los arreglos $I n D e g r ee$ InDegree y $O u t D e g r ee$ OutDegree. La cola $q$ se utiliza en el algoritmo de Kahn. En $p r o b [v]$ prob[v] calculamos la probabilidad de alcanzar el vértice $v$ .

vector<vector<int>> g;
vector<int> InDegree, OutDegree;
deque<int> q;
vector<double> prob;

Leer el número de islas $n$ , el número de puentes $m$ y el índice de la isla inicial $r$ . Inicializar la lista de adyacencia y los arreglos de grados.

scanf("%d %d %d", &n, &m, &r);
g.assign(n + 1, vector<int>());
InDegree.assign(n + 1, 0);
OutDegree.assign(n + 1, 0);

Leer los puentes y construir el grafo. Para cada arista $a \to b$ a \to b, aumentar el grado de salida del vértice $a$ y el grado de entrada del vértice $b$ .

for (i = 0; i < m; i++)
{
  scanf("%d %d", &a, &b);
  g[a].push_back(b);
  OutDegree[a]++;
  InDegree[b]++;
}

C++

Colocar en la cola todos los vértices con grado de entrada cero — el orden topológico comienza con ellos.

for (i = 1; i < InDegree.size(); i++)
  if (InDegree[i] == 0) q.push_back(i);

La probabilidad de estar en el vértice inicial $r$ es $1$ . Para todos los demás vértices la probabilidad inicial es $0$ : la función $r es i z e$ llena el arreglo $p r o b$ con ceros.

prob.resize(n + 1);
prob[r] = 1;

Ejecutar el algoritmo de Kahn. Los vértices se extraen de la cola en orden topológico.

while (!q.empty())
{

Extraer un vértice $v$ de la cola. En este momento, todos sus predecesores ya han sido procesados, por lo que el valor $p r o b [v]$ prob[v] es definitivo. Recorrer las aristas $(v, t o)$ (v, to). De vértice $v$ salen $O u t D e g r ee [v]$ OutDegree[v] aristas, y cada una de ellas se elige con igual probabilidad. Por lo tanto, nos movemos por la arista $v \to t o$ v \to to con probabilidad $p r o b [v] / O u t D e g r ee [v]$ prob[v] / OutDegree[v]. Sumar este valor a $p r o b [t o]$ prob[to].

  v = q.front(); q.pop_front();
  for (int to : g[v])
  {
    prob[to] += prob[v] / OutDegree[v];

Eliminar la arista $(v, t o)$ (v, to) del grafo — disminuir el grado de entrada del vértice $t o$ .

    InDegree[to]--;

Si el grado de entrada del vértice $t o$ se vuelve cero, todos sus predecesores han sido procesados y el valor $p r o b [t o]$ prob[to] es definitivo. Colocar $t o$ en la cola.

    if (InDegree[to] == 0) q.push_back(to);
  }
}

Encontrar la probabilidad máxima $m x$ entre los vértices sin salida — las islas $i$ sin puentes salientes ( $O u t D e g r ee [i] = 0$ OutDegree[i] = 0).

mx = 0;
for (i = 1; i <= n; i++)
  if (OutDegree[i] == 0 && prob[i] > mx) mx = max(mx, prob[i]);

Imprimir, en orden creciente, los índices de todos los vértices sin salida cuya probabilidad difiere de $m x$ en, como máximo, $E P S$ . Puede haber varios de estos vértices.

for (i = 1; i <= n; i++)
  if (OutDegree[i] == 0 && fabs(prob[i] - mx) <= EPS)
    printf("%d ", i);