Задача: дан ориентированный граф. У каждой вершины есть некая величина H, нужно для каждой вершины посчитать H', равное минимуму из всех значений H вершин, до которых можно добраться из текущей. Количество вершин и ребер до 10⁵.

Например, граф

1->2
2->3
2->5
3->4
5->6

H₁ = 3, H₂ = 30, H₃ = 5, H₄ = 1, H₅ = 20, H₆ = 10

Ответ:

H₁' = 1, H₂' = 1, H₃' = 1, H₄' = 1, H₅' = 10, H₆' = 10

И есть такое презабавное решение

G[N]; // список смежных вершин
H[N]; // те самые H
used[N] = {false}

dfs(v)
    used[v] = true
    suffle(G[v])
    for to in G[v]
        if used[to] = false
            dfs(to)
        H[v] = min(H[v], H[to])

main()
    for step = 0..25
        used = {false}
        P[N] = {0,1,2...,N-1}
        shuffle(P)
        for v in P
            dfs(v)

Завалить решение без shuffle довольно просто, а как быть с shuffle? Кто-нибудь умеет делать тесты для подобных решений? Или кто-нибудь может посчитать вероятность того, что решение выдаст правильный ответ? =)