Fuga del Boss#9888

Fuga del Boss (Editoriale)

I rifugi e i passaggi formano un albero di $n$ vertici. Bloccare un passaggio equivale a rimuovere un arco. È richiesto aggiungere il minor numero possibile di archi in modo che, dopo la rimozione di un qualsiasi arco, il grafo rimanga connesso, cioè che non contenga ponti. Se il grafo rimane connesso, allora da qualsiasi rifugio si può raggiungere il quartier generale, quindi il numero del quartier generale $h$ non influisce sulla risposta.

Stima inferiore. Chiamiamo foglia un vertice di grado $1$ , e sia $L$ il numero di foglie nell'albero. L'unico arco che esce da una foglia è un ponte. Affinché smetta di essere un ponte, è necessario tracciare verso la foglia almeno un nuovo arco. Ogni nuovo arco ha due estremità, quindi copre al massimo due foglie. Dunque saranno necessari almeno $⌈ L /2 ⌉$ nuovi archi.

Costruzione. Dimostriamo che $⌈ L /2 ⌉$ archi sono sempre sufficienti. Avviamo una ricerca in profondità da un vertice qualsiasi ed elenchiamo le foglie nell'ordine in cui vengono visitate: $l_{0}, l_{1}, ..., l_{L - 1}$ l_0, l_1, ..., l_{L-1}. Indichiamo $k = ⌊ L /2 ⌋$ k = \lfloor L / 2 \rfloor e colleghiamo le foglie i cui numeri in questo elenco differiscono di $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}

Si ottengono esattamente $⌈ L /2 ⌉$ archi, e ogni foglia risulta essere estremità di almeno uno di essi. Se $L$ è dispari, la foglia $l_{k}$ l_k partecipa a due archi.

Esempio. Nella figura $L = 5$ L = 5 e $k = 2$ k = 2. Le foglie sono colorate, e accanto a ciascuna è indicato il suo numero nell'ordine di visita. Gli archi aggiunti $(3, 5), (4, 7)$ (3, 5), (4, 7) e $(5, 8)$ sono mostrati tratteggiati, la foglia $5$ partecipa a due di essi.

Perché non restano ponti. Appendiamo l'albero per il vertice da cui è partita la ricerca. L'arco dell'albero ( $v$ , genitore di $v$ ) smette di essere un ponte se almeno un nuovo arco collega una foglia all'interno del sottoalbero di $v$ con una foglia al di fuori di esso. La ricerca in profondità visita il sottoalbero di $v$ interamente, senza interruzioni, quindi le foglie di questo sottoalbero compaiono nell'elenco consecutivamente e occupano un segmento di lunghezza $s$ . Nel sottoalbero c'è almeno una foglia, ma tutte le $L$ foglie non possono trovarsi al suo interno: o la radice ha altri sottoalberi con proprie foglie, oppure la radice stessa è una foglia. Perciò $1 \leq s \leq L - 1$ 1 \le s \le L - 1.

Il partner di ogni foglia nel nuovo arco si trova a esattamente $k$ posizioni di distanza da essa nell'elenco. Consideriamo due casi:

$s \leq k$ s \le k. Il partner della prima foglia del segmento si trova a distanza $k \geq s$ k \ge s da essa, cioè al di fuori del segmento;
$s > k$ s > k. Al di fuori del segmento si trovano $L - s \leq L - k - 1 \leq k$ L - s \le L - k - 1 \le k foglie. Prendiamone una qualsiasi. Il suo partner si trova a $k$ posizioni di distanza da essa, ma al di fuori del segmento non ci sono due foglie a tale distanza. Perciò il partner si trova all'interno del segmento.

In entrambi i casi si troverà un nuovo arco che collega il sottoalbero di v con il resto dell'albero. Dunque, nessun arco rimarrà un ponte.

Teorema. Il numero minimo di nuovi archi è pari a $⌈ L /2 ⌉$ . È sufficiente elencare le foglie nell'ordine della ricerca in profondità e collegare ogni foglia $l_{i}$ l_i con la foglia $l_{i} + ⌊ L /2 ⌋$ l_i + \lfloor L / 2 \rfloor per $i = 0, 1, ..., ⌈ L /2 ⌉ - 1$ i = 0, 1, ..., \lceil L / 2 \rceil - 1.

Per $n = 2$ n = 2 entrambe le estremità dell'unico arco sono foglie, e la risposta sarà un secondo arco tra di esse.

Esempio

Nel primo esempio, la ricerca a partire dal vertice $0$ visita le foglie nell'ordine $1, 2, 3$ . Qui $L = 3, k = 1$ L = 3, k = 1, e il programma aggiunge gli archi $(1, 2)$ e $(2, 3)$ :

La risposta differisce da quella fornita nel testo del problema, ma è comunque corretta: va bene qualsiasi insieme corretto di due archi.

Nel secondo esempio, le foglie nell'ordine di visita sono: $4, 5, 2, 3$ 4, 5, 2, 3. Qui $L = 4, k = 2$ L = 4, k = 2:

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

Colleghiamo $l_{0} - l_{2}$ l_0 - l_2 e $l_{1} - l_{3}$ l_1 - l_3, cioè aggiungiamo gli archi $(4, 2)$ e $(5, 3)$ :

Verifichiamo, ad esempio, l'arco $(0, 1)$ . Le foglie del sottoalbero del vertice $1$ sono $4$ e $5$ , che occupano nell'elenco il segmento delle posizioni $0$ e $1$ . L'arco $(4, 2)$ esce da questo sottoalbero, quindi l'arco $(0, 1)$ non è un ponte.

Implementazione dell'algoritmo

Memorizziamo l'albero come lista di adiacenza $g$ . Le foglie nell'ordine della visita in profondità vengono raccolte nell'array $l e a v es$ .

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

La funzione dfs esegue la ricerca in profondità a partire dal vertice $v$ . Il parametro $p$ è il genitore del vertice $v$ , per la radice $p = - 1$ p = -1. Per prima cosa visitiamo tutti i figli del vertice $v$ .

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

Un vertice di grado $1$ è una foglia, lo inseriamo nell'array $l e a v es$ . Le foglie di qualsiasi sottoalbero finiscono nell'array consecutivamente.

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

Parte principale del programma. Leggiamo i dati in input. Il numero del quartier generale $h$ non influisce sulla risposta.

  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++

Avviamo la ricerca in profondità dal vertice $0$ e raccogliamo le foglie. La variabile $m$ contiene il numero di foglie, e $r = ⌈ m /2 ⌉$ r = \lceil m / 2 \rceil è il numero di nuovi passaggi.

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

Stampiamo la risposta: la foglia con numero $i$ nell'elenco viene collegata alla foglia con numero $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]);