Isola solitaria#9044

Isola solitaria (Editoriale)

Per l'enunciato del problema, una volta lasciata un'isola non è mai più possibile tornarci. Quindi il grafo i cui vertici sono le isole e i cui archi sono i ponti è un grafo diretto aciclico. Ci si può bloccare solo su un'isola $v$ priva di ponti in uscita, cioè in un vertice senza uscita con grado uscente zero: $O u t D e g r ee [v] = 0$ OutDegree[v] = 0.

Sia $p r o b [v]$ prob[v] la probabilità che durante il percorso si raggiunga il vertice $v$ . Per il vertice di partenza $p r o b [r] = 1$ prob[r] = 1; per tutti gli altri vertici inizialmente $p r o b [v] = 0$ prob[v] = 0. Poiché il grafo non contiene cicli, ogni vertice può essere visitato al massimo una volta.

Supponiamo che da un vertice $u$ escano $O u t D e g r ee [u]$ OutDegree[u] archi. Trovandoci in $u$ , ne scegliamo uno uniformemente a caso, quindi ci spostiamo lungo ciascun arco $u \to v$ u \to v con probabilità $p r o b [u] / O u t D e g r ee [u]$ prob[u] / OutDegree[u]. Il vertice $v$ può essere raggiunto solo dai suoi predecessori diretti. Pertanto $p r o b [v]$ prob[v] è uguale alla somma dei contributi di tutti gli archi $u \to v$ u \to v entranti in $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]

Il valore $p r o b [v]$ prob[v] può essere calcolato solo quando le probabilità di tutti i suoi predecessori sono definitive. Questo è esattamente l'ordine di elaborazione fornito da un ordinamento topologico: ogni vertice compare dopo tutti i vertici da cui partono archi verso di esso. Pertanto costruiamo l'ordine topologico tramite l'algoritmo di Kahn e contemporaneamente "spingiamo" le probabilità lungo gli archi.

L'algoritmo è il seguente:

per ogni vertice $v$ , calcolare il suo grado entrante $I n D e g r ee [v]$ InDegree[v] e il suo grado uscente $O u t D e g r ee [v]$ OutDegree[v];
inserire nella coda tutti i vertici con grado entrante zero e impostare $p r o b [r] = 1$ prob[r] = 1;
finché la coda non è vuota, estrarre da essa un vertice $v$ . A questo punto tutti i suoi predecessori sono già stati elaborati, quindi il valore $p r o b [v]$ prob[v] è definitivo. Per ogni arco $v \to t o$ v \to to, aggiungere $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] e diminuire $I n D e g r ee [t o]$ InDegree[to] di $1$ . Se il grado entrante del vertice $t o$ diventa zero, inserirlo nella coda.

Inizialmente, la coda contiene tutti i vertici con grado entrante zero, non solo quello di partenza. Vengono elaborati anche i vertici non raggiungibili da $r$ , ma la loro probabilità rimane zero e non influisce sulla risposta.

Ricerca della risposta. Tra i vertici senza uscita, trovare la probabilità massima $m x$ . Quindi stampare, in ordine crescente, gli indici di tutti i vertici senza uscita $v$ tali che $∣ p r o b [v] - m x ∣ \leq 1 0^{- 9}$ |prob[v] - mx| \le 10^{-9}. Il confronto con una tolleranza è necessario poiché le probabilità vengono calcolate con numeri in virgola mobile soggetti a errori di arrotondamento.

Complessità. Ogni vertice viene inserito ed estratto dalla coda esattamente una volta, e ogni arco viene esaminato una volta. Il tempo di esecuzione dell'algoritmo è $O (n + m)$ O(n + m).

Esempio

Simuliamo l'algoritmo sul grafo dell'esempio. Accanto a ogni vertice è indicata la probabilità $p r o b [v]$ prob[v] di raggiungerlo. I vertici elaborati sono ombreggiati in grigio, gli archi lungo i quali la probabilità viene distribuita al passo corrente sono evidenziati in blu, e gli archi già esaminati sono disegnati tratteggiati.

Inizialmente (figura a sinistra) $p r o b [1] = 1$ prob[1] = 1, e le probabilità di tutti gli altri vertici sono $0$ . Il vertice $1$ è l'unico vertice con grado entrante zero, quindi è il primo a essere estratto dalla coda.

Dal vertice $1$ escono quattro archi, quindi la probabilità $p r o b [1] = 1$ prob[1] = 1 viene suddivisa equamente tra i vertici $2, 3, 4$ e $5$ : ciascuno di essi riceve $1/4 = 0.25$ 1 / 4 = 0.25 (figura a destra). Dopo aver rimosso gli archi uscenti dal vertice $1$ , i gradi entranti dei vertici $2$ e $3$ diventano zero, e vengono inseriti nella coda.

Successivamente viene elaborato il vertice $2$ . Da esso escono due archi, quindi $p r o b [2] /2 = 0.25/2 = 0.125$ prob[2] / 2 = 0.25 / 2 = 0.125 viene aggiunto a $p r o b [4]$ e $p r o b [5]$ . Otteniamo $p r o b [4] = p r o b [5] = 0.375$ prob[4] = prob[5] = 0.375 (figura in basso a sinistra). Il grado entrante del vertice $5$ diventa zero, e viene inserito nella coda.

Viene elaborato poi il vertice $3$ . Da esso esce un singolo arco $3 \to 4$ 3 \to 4, quindi $p r o b [4]$ aumenta di $p r o b [3] /1 = 0.25$ prob[3] / 1 = 0.25 e diventa $0.625$ (figura in basso a destra). Ora anche il vertice $4$ viene inserito nella coda.

I vertici $5$ e $4$ non hanno archi uscenti, quindi la loro elaborazione non modifica alcuna probabilità. L'ordine topologico risultante è $1, 2, 3, 5, 4$ 1, 2, 3, 5, 4.

I vertici senza uscita sono $4$ e $5$ , con probabilità rispettivamente $0.625$ e $0.375$ . La loro somma è uguale a $1$ : siamo certi di bloccarci da qualche parte. La probabilità massima è raggiunta dal singolo vertice $4$ , che è la risposta.

Implementazione dell'algoritmo

Dichiarare la costante $E P S$ — la tolleranza per il confronto di numeri in virgola mobile.

#define EPS 1e-9

Memorizzare il grafo di input come lista di adiacenza $g$ . Memorizzare i gradi entranti e uscenti dei vertici negli array $I n D e g r ee$ InDegree e $O u t D e g r ee$ OutDegree. La coda $q$ viene utilizzata nell'algoritmo di Kahn. In $p r o b [v]$ prob[v] calcoliamo la probabilità di raggiungere il vertice $v$ .

vector\u003cvector\u003cint\u003e\u003e g;
vector\u003cint\u003e InDegree, OutDegree;
deque\u003cint\u003e q;
vector\u003cdouble\u003e prob;

Leggere il numero di isole $n$ , il numero di ponti $m$ e l'indice dell'isola di partenza $r$ . Inizializzare la lista di adiacenza e gli array dei gradi.

scanf("%d %d %d", \u0026n, \u0026m, \u0026r);
g.assign(n + 1, vector\u003cint\u003e());
InDegree.assign(n + 1, 0);
OutDegree.assign(n + 1, 0);

Leggere i ponti e costruire il grafo. Per ogni arco $a \to b$ a \to b, aumentare il grado uscente del vertice $a$ e il grado entrante del vertice $b$ .

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

C++

Inserire nella coda tutti i vertici con grado entrante zero — l'ordinamento topologico inizia da essi.

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

La probabilità di trovarsi nel vertice di partenza $r$ è $1$ . Per tutti gli altri vertici la probabilità iniziale è $0$ : la funzione $r es i z e$ riempie l'array $p r o b$ con zeri.

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

Eseguire l'algoritmo di Kahn. I vertici vengono estratti dalla coda in ordine topologico.

while (!q.empty())
{

Estrarre un vertice $v$ dalla coda. A questo punto tutti i suoi predecessori sono già stati elaborati, quindi il valore $p r o b [v]$ prob[v] è definitivo. Scorrere gli archi $(v, t o)$ (v, to). Dal vertice $v$ escono $O u t D e g r ee [v]$ OutDegree[v] archi, e ciascuno di essi viene scelto con uguale probabilità. Pertanto ci spostiamo lungo l'arco $v \to t o$ v \to to con probabilità $p r o b [v] / O u t D e g r ee [v]$ prob[v] / OutDegree[v]. Aggiungere questo valore 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];

Rimuovere l'arco $(v, t o)$ (v, to) dal grafo — diminuire il grado entrante del vertice $t o$ .

    InDegree[to]--;

Se il grado entrante del vertice $t o$ diventa zero, tutti i suoi predecessori sono stati elaborati e il valore $p r o b [t o]$ prob[to] è definitivo. Inserire $t o$ nella coda.

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

Trovare la probabilità massima $m x$ tra i vertici senza uscita — le isole $i$ prive di ponti in uscita ( $O u t D e g r ee [i] = 0$ OutDegree[i] = 0).

mx = 0;
for (i = 1; i \u003c= n; i++)
  if (OutDegree[i] == 0 \u0026\u0026 prob[i] \u003e mx) mx = max(mx, prob[i]);

Stampare, in ordine crescente, gli indici di tutti i vertici senza uscita la cui probabilità differisce da $m x$ al massimo di $E P S$ . Potrebbero esserci più vertici di questo tipo.

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