Lonely Island#9044

Lonely Island (Editorial)

By the problem statement, once you leave an island you can never return to it. Hence the graph whose vertices are the islands and whose edges are the bridges is a directed acyclic graph. You can get stuck only on an island $v$ with no outgoing bridges, that is, in a dead-end vertex with zero out-degree: $O u t D e g r ee [v] = 0$ OutDegree[v] = 0.

Let $p r o b [v]$ prob[v] denote the probability that during the walk we reach vertex $v$ . For the starting vertex $p r o b [r] = 1$ prob[r] = 1; for all other vertices initially $p r o b [v] = 0$ prob[v] = 0. Since the graph contains no cycles, each vertex can be visited at most once.

Suppose $O u t D e g r ee [u]$ OutDegree[u] edges leave vertex $u$ . Being at $u$ , we choose one of them uniformly at random, so we move along each edge $u \to v$ u \to v with probability $p r o b [u] / O u t D e g r ee [u]$ prob[u] / OutDegree[u]. Vertex $v$ can be reached only from its direct predecessors. Therefore, $p r o b [v]$ prob[v] equals the sum of the contributions of all edges $u \to v$ u \to v entering $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]

The value $p r o b [v]$ prob[v] can be computed only when the probabilities of all its predecessors are final. This is exactly the processing order given by a topological sort: every vertex appears after all vertices from which edges lead into it. Therefore, we build the topological order using Kahn's algorithm and at the same time "push" the probabilities along the edges.

The algorithm is as follows:

for each vertex $v$ , compute its in-degree $I n D e g r ee [v]$ InDegree[v] and out-degree $O u t D e g r ee [v]$ OutDegree[v];
push all vertices with zero in-degree into the queue and set $p r o b [r] = 1$ prob[r] = 1;
while the queue is not empty, extract a vertex $v$ from it. By this moment all its predecessors have already been processed, so the value $p r o b [v]$ prob[v] is final. For each edge $v \to t o$ v \to to, add $p r o b [v] / O u t D e g r ee [v]$ prob[v] / OutDegree[v] to $p r o b [t o]$ prob[to] and decrease $I n D e g r ee [t o]$ InDegree[to] by $1$ . If the in-degree of vertex $t o$ becomes zero, push it into the queue.

Initially, the queue contains all vertices with zero in-degree, not only the starting one. Vertices unreachable from $r$ are processed as well, but their probability remains zero and does not affect the answer.

Finding the answer. Among the dead-end vertices, find the maximum probability $m x$ . Then print, in increasing order, the indices of all dead-end vertices $v$ such that $∣ p r o b [v] - m x ∣ \leq 1 0^{- 9}$ |prob[v] - mx| \le 10^{-9}. Comparison with a tolerance is necessary because the probabilities are computed in floating-point numbers with rounding errors.

Complexity. Each vertex is pushed into and extracted from the queue exactly once, and each edge is examined once. The running time of the algorithm is $O (n + m)$ O(n + m).

Example

Let us simulate the algorithm on the graph from the example. Next to each vertex, the probability $p r o b [v]$ prob[v] of reaching it is shown. Processed vertices are shaded gray, the edges along which the probability is distributed at the current step are highlighted in blue, and already examined edges are drawn dashed.

Initially (left figure) $p r o b [1] = 1$ prob[1] = 1, and the probabilities of all other vertices are $0$ . Vertex $1$ is the only vertex with zero in-degree, so it is the first to be extracted from the queue.

Four edges leave vertex $1$ , so the probability $p r o b [1] = 1$ prob[1] = 1 is split equally among vertices $2, 3, 4$ and $5$ : each of them receives $1/4 = 0.25$ 1 / 4 = 0.25 (right figure). After removing the edges leaving vertex $1$ , the in-degrees of vertices $2$ and $3$ become zero, and they are pushed into the queue.

Next, vertex $2$ is processed. Two edges leave it, so $p r o b [2] /2 = 0.25/2 = 0.125$ prob[2] / 2 = 0.25 / 2 = 0.125 is added to $p r o b [4]$ and $p r o b [5]$ . We get $p r o b [4] = p r o b [5] = 0.375$ prob[4] = prob[5] = 0.375 (bottom left figure). The in-degree of vertex $5$ becomes zero, and it is pushed into the queue.

Vertex $3$ is processed next. A single edge $3 \to 4$ 3 \to 4 leaves it, so $p r o b [4]$ increases by $p r o b [3] /1 = 0.25$ prob[3] / 1 = 0.25 and becomes $0.625$ (bottom right figure). Now vertex $4$ is pushed into the queue as well.

Vertices $5$ and $4$ have no outgoing edges, so processing them does not change any probabilities. The resulting topological order is $1, 2, 3, 5, 4$ 1, 2, 3, 5, 4.

The dead-end vertices are $4$ and $5$ , with probabilities $0.625$ and $0.375$ respectively. Their sum equals $1$ : we are certain to get stuck somewhere. The maximum probability is reached at the single vertex $4$ , which is the answer.

Algorithm implementation

Declare the constant $E P S$ — the tolerance for comparing floating-point numbers.

#define EPS 1e-9

Store the input graph as an adjacency list $g$ . Store the in-degrees and out-degrees of the vertices in the arrays $I n D e g r ee$ InDegree and $O u t D e g r ee$ OutDegree. The queue $q$ is used in Kahn's algorithm. In $p r o b [v]$ prob[v] we compute the probability of reaching vertex $v$ .

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

Read the number of islands $n$ , the number of bridges $m$ and the index of the starting island $r$ . Initialize the adjacency list and the degree arrays.

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

Read the bridges and build the graph. For each edge $a \to b$ a \to b, increase the out-degree of vertex $a$ and the in-degree of vertex $b$ .

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

C++

Push all vertices with zero in-degree into the queue — the topological sort starts with them.

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

The probability of being at the starting vertex $r$ is $1$ . For all other vertices the initial probability is $0$ : the function $r es i z e$ fills the array $p r o b$ with zeros.

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

Run Kahn's algorithm. Vertices are extracted from the queue in topological order.

while (!q.empty())
{

Extract a vertex $v$ from the queue. By this moment all its predecessors have already been processed, so the value $p r o b [v]$ prob[v] is final. Iterate over the edges $(v, t o)$ (v, to). $O u t D e g r ee [v]$ OutDegree[v] edges leave vertex $v$ , and each of them is chosen with equal probability. Therefore, we move along the edge $v \to t o$ v \to to with probability $p r o b [v] / O u t D e g r ee [v]$ prob[v] / OutDegree[v]. Add this value to $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];

Remove the edge $(v, t o)$ (v, to) from the graph — decrease the in-degree of vertex $t o$ .

    InDegree[to]--;

If the in-degree of vertex $t o$ becomes zero, all its predecessors have been processed and the value $p r o b [t o]$ prob[to] is final. Push $t o$ into the queue.

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

Find the maximum probability $m x$ among the dead-end vertices — the islands $i$ with no outgoing bridges ( $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]);

Print, in increasing order, the indices of all dead-end vertices whose probability differs from $m x$ by at most $E P S$ . There may be several such vertices.

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