Quarantraining - 07

DFS Tree

Prerequisiti

  • Depth-First Search

Introduzione

L’intero post è riadattato da qui. Avendo trovato molto interessante il blog su Codeforces ho pensato di riproporlo in italiano per renderlo più accessibile. Verranno presentati alcuni usi del DFS Tree per risolvere problemi che altrimenti potrebbero risultare tediosi da scrivere. Inoltre, il meccanismo dietro queste soluzioni non è solo facile da implementare, ma anche estremamente facile da capire e può dare una prospettiva più chiara sul problema.

Il DFS Tree

Supponiamo di avere un grafo non diretto e connesso G, con N nodi e M archi. Eseguiamo ora una DFS del grafo, partendo dal nodo in cui vogliamo ancorare il DFS tree. Ogni volta che percorriamo un arco, se porta a un nodo già visitato, lo contrassegnamo come “Span Edge”, ovvero un arco che appartiene al DFS tree.
Ogni arco che non è uno span edge viene detto “Back Edge”.
In C++, la funzione sarà simile a:

bool visitato[N]; // usato per sapere se un nodo è già stato visitato
bool span_edges[M]; // gli span edges avranno valore "true", i back "edges false"
vector<pair<int,int>> adj[N]; // liste di adiacenza del grafo, ogni pair sarà del tipo {nodo a cui porta, indice dell'arco}
void dfs(int nodo){
  visitato[nodo] = true;
  for(auto x: adj[nodo]){
    if(visitato[x.first])continue; //non dobbiamo processare due volte uno stesso nodo
    span_edge[x.second] = true;
    dfs(x.first);
  }
}

Possiamo fare alcune osservazioni, estremamente facili da verificare:

  1. Gli span edges formano un albero, difatti sono N-1 poichè viene aggiunto uno span edge ogni prima volta che un nodo diverso dalla radice viene visitato e ogni nodo viene visitato, essendo G connesso.

  2. Tutti i back edges connettono un nodo a un suo ancestor o discendente nel DFS tree. Supponiamo che esista un arco ab tale che a non sia un discendente o un ancestor di b. Supponiamo inoltre, senza perdita di generalità, che a venga visitato prima di b. Quando viene processato l’arco ab: se b non è ancora stato visitato, ab è uno span edge, altrimenti, poichè dfs(b) è stata chiamata dopo dfs(a) ma prima della sua conclusione, b appartiene al sottoalbero di a e ne è quindi discendente.
    Abbiamo raggiunto un assurdo, quindi ogni arco nel nostro albero connette due nodi che sono uno discendente dell’altro.

Questa è un’ animazione di come agisce la DFS, gli span edges vengono segnati in grassetto.

Trovare i ponti con il DFS tree

In un grafo indiretto connesso, un ponte è un arco la quale rimozione renderebbe il grafo non connesso.
Una volta costruito il DFS tree, quali possono essere i ponti?

Osservazione 1

Un back edge non può essere un ponte, infatti connette nodi già connessi da uno o più span edges.

Osservazione 2

Uno span edge è un ponte se e solo se non ci sono back edges che connettono un suo discendente a un suo ancestor.

Dunque, come capire se un nodo non ha back edges che vi “passano sopra”?
Si può usare la programmazione dinamica sull’albero, considerando per ogni nodo il numero di back edges che partono da un suo discendente e arrivano a un suo predecessore.
Se dp[i]=0, allora l’arco che connette i a suo padre è un ponte.
Questa dp è facilmente calcolabile. In C++, il codice può essere scritto come:

vector<int> ponti; // salviamo in questo vettore i nodi i tali che dp[i]=0
bool visitato2[N];
int dp[N];
void trova_ponti(int nodo){
  visitato2[nodo] = 1;
  for(auto x: adj[i]){
    if(!span_edge[x.second]){
      if(visitato2[x.first])dp[nodo]++; //i nodi già visitati sono predecessori
      else dp[nodo]--;                  //quelli non visitati discendenti
    }else{
      if(!visitato2[x.first]){
        trova_ponti(x.first);
        dp[nodo]+=dp[x.first];
      }
    }
  }
  if(dp[nodo]==0)ponti.push_back(nodo);
}

Per ogni nodo, dp[i] può essere calcolato come somma di dp fra i suoi figli, a cui va aggiunto il numero di back edges che connettono i a un suo ancestor e sottratto il numero di quelli che portano a un suo discendente.

Processare i cactus con il DFS tree

Un cactus è un grafo indiretto connesso in cui ogni nodo appartiene a al più un ciclo.
Per trattare questo tipo di grafo è spesso utile comprimere tutti i nodi appartenenti allo stesso ciclo in un unico nodo.
Il DFS tree consente di eseguire questa operazione molto comodamente:
Poichè ogni nodo può appartener ad al più un ciclo, ci sarà al più un back edge che passa sopra ogni nodo. Inoltre, tutti i nodi sotto lo stesso back edge appartengono allo stesso ciclo e se su un nodo non passano back edges, esso non appartiene ad alcun ciclo.

Problemi correlati

Problemi che possono essere risolti usando il DFS tree, su codeforces.
231 E
858 F
1325 F

11 Mi Piace

Un esercizio carino su cui provare il dfs tree presente sul cms è inviti alla festa. Per risolverlo non è strettamente necessario, ma una volta scritta la soluzione esce elegante. Eventualmente sono disposto a condividere il mio approccio per quel esercizio :grin:

1 Mi Piace

Lo condivida pure :new_moon_with_face:

1 Mi Piace

Mi vuoi far proprio scrivere :new_moon_with_face:
In inviti alla festa ci è richiesto di contare quante persone possono essere invitate alla festa al più. Il criterio secondo il quale una persona può essere invitato è che siano presenti almeno altri due amici alla festa. Quindi, automaticamente, tutti coloro che hanno solo un amico non sono invitati. A questo punto può capitare che una persona che precedentemente aveva due amici può averne perso uno e di conseguenza anch’essa non potrà più partecipare; scatenando eventualmente un effetto a catena. Proviamo dunque a eseguire questo procedimento su un generico grafo, e noteremo che alla fine solo i nodi che formano un ciclo sono presenti.
Il problema ora è diventato: Quanti nodi appartengono ad almeno un ciclo?
E qui che ci viene in aiuto il dfs tree con i suoi spanning edges e i back edges. Una volta realizzato uno spanning tree qualsiasi, è facile notare che solo i back edges creano cicli e tali cicli comprendono tutti nodi racchiusi nel ramo che parte da un estremo e arriva all’altro del back edge.
Ora la sfida è come marchiare questi nodi in modo efficiente. Una prima soluzione sarebbe ripercorrere l’albero/visitare lo stack delle chiamate per marchiare i nodi totalizzando una complessità di O(N \times numeroCicli). Soluzione sufficiente per il problema ma non soddisfacente.
Qua entra in gioco un piccolo trick proveniente da una nostra vecchia conoscenza, la suffix sum!
Questo trick lo si può attuare proprio perché realizzando un dfs tree siamo riusciti a direzionare il grafo e a stabilire una relazione di parentela. Ogni nodo che possiede un back edge guadagna 1 mentre ogni genitore dell’estremo del back edge perde 1.
È proprio il genitore del estremo del back edge poiché l’estremo è compreso nel ciclo mentre il genitore no.
Ora, partendo delle foglie, basta accumulare questi valori e tutti i nodi che hanno un contatore positivo apparterranno ad almeno un ciclo.
Una prima soluzione di accumulare le somme dei contatori è elaborare i nodi per altezza del dfs tree, soluzione efficiente O(N logN) ma si può fare ancora di meglio. Basta notare che durante la visita del dfs tree processiamo già i nodi in ordine di altezza, quindi con una piccola modifica, riusciamo a totalizzare una complessità di O(N +M) che ci permette di risolvere il problema con assunzioni molto più grandi di quelle proposte.
Questo è il cuore del ragionamento, dovreste riuscire a fare tipo 10pt implementando ciò indicato. Bisogna far attenzione a due particolari per ottenere il 100 che non vi spoilero per farvi esercitare :stuck_out_tongue:
Piccolo spoiler nel caso in cui non riuscite a trovarli:

Cosa succede se il grafo è un bamboo(albero in cui il grado massimo di un nodo è 2)?

Cosa succede se il grafo è un generico albero?

Cosa succede se il grafo è una catena?

Ti ricordo che il grafo non è connesso!

2 Mi Piace