Fuga del Cabecilla#9888

Fuga del Cabecilla (Editorial)

Los refugios y los pasajes forman un árbol de $n$ vértices. Bloquear un pasaje equivale a eliminar una arista. Se requiere añadir la menor cantidad de aristas de modo que, tras eliminar cualquier arista, el grafo siga siendo conexo, es decir, que no tenga puentes. Si el grafo permanece conexo, entonces desde cualquier refugio se puede llegar al cuartel general, por lo que el número del cuartel general $h$ no afecta la respuesta.

Cota inferior. Llamemos hoja a un vértice de grado $1$ , y supongamos que en el árbol hay $L$ hojas. La única arista que sale de una hoja es un puente. Para que deje de ser un puente, es necesario trazar al menos una nueva arista hacia esa hoja. Cada nueva arista tiene dos extremos, por lo que cubre a lo sumo dos hojas. Por lo tanto, se necesitarán al menos $⌈ L /2 ⌉$ nuevas aristas.

Construcción. Mostremos que $⌈ L /2 ⌉$ aristas siempre son suficientes. Ejecutemos una búsqueda en profundidad desde cualquier vértice y anotemos las hojas en el orden en que se recorren: $l_{0}, l_{1}, ..., l_{L - 1}$ l_0, l_1, ..., l_{L-1}. Denotemos $k = ⌊ L /2 ⌋$ k = \lfloor L / 2 \rfloor y conectemos las hojas cuyos números en esta lista difieren en $k$ :

l_{0} - l_{k}, l_{1} - l_{k + 1}, ..., l_{⌈ L /2 ⌉ - 1} - l_{⌈ L /2 ⌉ - 1 + k}

l_0 - l_k, l_1 - l_{k+1}, ..., l_{\lceil L / 2 \rceil - 1} - l_{\lceil L / 2 \rceil - 1 + k}

Se obtienen exactamente $⌈ L /2 ⌉$ aristas, y cada hoja resulta ser el extremo de al menos una de ellas. Si $L$ es impar, la hoja $l_{k}$ l_k participa en dos aristas.

Ejemplo. En la figura $L = 5$ L = 5 y $k = 2$ k = 2. Las hojas están coloreadas, y junto a cada una se indica su número en el orden de recorrido. Las aristas añadidas $(3, 5), (4, 7)$ (3, 5), (4, 7) y $(5, 8)$ se muestran punteadas, la hoja $5$ participa en dos de ellas.

Por qué no quedan puentes. Colguemos el árbol desde el vértice del cual se inició la búsqueda. La arista del árbol ( $v$ , padre de $v$ ) deja de ser un puente si al menos una nueva arista conecta una hoja dentro del subárbol de $v$ con una hoja fuera de él. La búsqueda en profundidad recorre el subárbol de $v$ por completo, sin interrupciones, por lo que las hojas de este subárbol aparecen consecutivas en la lista y ocupan un segmento de longitud $s$ . En el subárbol hay al menos una hoja, y no pueden estar en él las $L$ hojas: o bien la raíz tiene otros subárboles con sus propias hojas, o bien la raíz misma es una hoja. Por lo tanto, $1 \leq s \leq L - 1$ 1 \le s \le L - 1.

El compañero de cada hoja en la nueva arista está a exactamente $k$ posiciones de distancia en la lista. Consideremos dos casos:

$s \leq k$ s \le k. El compañero de la primera hoja del segmento se encuentra a una distancia $k \geq s$ k \ge s de ella, es decir, fuera del segmento;
$s > k$ s > k. Fuera del segmento se encuentran $L - s \leq L - k - 1 \leq k$ L - s \le L - k - 1 \le k hojas. Tomemos cualquiera de ellas. Su compañero está a $k$ posiciones de distancia, y fuera del segmento no hay dos hojas a esa distancia. Por lo tanto, el compañero se encuentra dentro del segmento.

En ambos casos se encontrará una nueva arista que conecta el subárbol de v con el resto del árbol. Por lo tanto, ninguna arista seguirá siendo un puente.

Teorema. La menor cantidad de nuevas aristas es igual a $⌈ L /2 ⌉$ . Basta con anotar las hojas en el orden de la búsqueda en profundidad y conectar cada hoja $l_{i}$ l_i con la hoja $l_{i} + ⌊ L /2 ⌋$ l_i + \lfloor L / 2 \rfloor para $i = 0, 1, ..., ⌈ L /2 ⌉ - 1$ i = 0, 1, ..., \lceil L / 2 \rceil - 1.

Cuando $n = 2$ n = 2, ambos extremos de la única arista son hojas, y la respuesta será una segunda arista entre ellos.

Ejemplo

En el primer ejemplo, la búsqueda desde el vértice $0$ recorre las hojas en el orden $1, 2, 3$ . Aquí $L = 3, k = 1$ L = 3, k = 1, y el programa añade las aristas $(1, 2)$ y $(2, 3)$ :

La respuesta difiere de la indicada en el enunciado, pero también es correcta: sirve cualquier conjunto válido de dos aristas.

En el segundo ejemplo, las hojas en orden de recorrido son: $4, 5, 2, 3$ 4, 5, 2, 3. Aquí $L = 4, k = 2$ L = 4, k = 2:

$i$	0	1	2	3
$l_{i}$ l_i	4	5	2	3

Conectamos $l_{0} - l_{2}$ l_0 - l_2 y $l_{1} - l_{3}$ l_1 - l_3, es decir, añadimos las aristas $(4, 2)$ y $(5, 3)$ :

Comprobemos, por ejemplo, la arista $(0, 1)$ . Las hojas del subárbol del vértice $1$ son $4$ y $5$ , que ocupan en la lista el segmento de las posiciones $0$ y $1$ . La arista $(4, 2)$ sale de este subárbol, por lo que la arista $(0, 1)$ no es un puente.

Implementación del algoritmo

El árbol se almacena como una lista de adyacencia $g$ . Las hojas en orden de recorrido en profundidad se recopilan en el arreglo $l e a v es$ .

vector<vector<int>> g;
vector<int> leaves;

La función dfs realiza una búsqueda en profundidad desde el vértice $v$ . El parámetro $p$ es el padre del vértice $v$ , para la raíz $p = - 1$ p = -1. Primero recorremos todos los hijos del vértice $v$ .

void dfs(int v, int p = -1)
{
  for (int to : g[v])
    if (to != p) dfs(to, v);

Un vértice de grado $1$ es una hoja, lo agregamos al arreglo $l e a v es$ . Las hojas de cualquier subárbol caen consecutivas en el arreglo.

  if (g[v].size() == 1)
    leaves.push_back(v);
}

Parte principal del programa. Leemos los datos de entrada. El número del cuartel general $h$ no afecta la respuesta.

  scanf("%d %d", &n, &h);
  g.resize(n);
  for (i = 1; i < n; i++)
  {
    scanf("%d %d", &a, &b);
    g[a].push_back(b);
    g[b].push_back(a);
  }

C++

Ejecutamos la búsqueda en profundidad desde el vértice $0$ y recopilamos las hojas. La variable $m$ contiene la cantidad de hojas, y $r = ⌈ m /2 ⌉$ r = \lceil m / 2 \rceil es la cantidad de nuevos pasajes.

  dfs(0);
  m = leaves.size();
  r = (m + 1) / 2;

Mostramos la respuesta: la hoja con número $i$ en la lista se conecta con la hoja con número $i + ⌊ m /2 ⌋$ i + \lfloor m / 2 \rfloor.

  printf("%d\n", r);
  for (i = 0; i < r; i++)
    printf("%d %d\n", leaves[i], leaves[i + m / 2]);