Как Флойдом-Уоршеллом построить транзитивное замыкание (достижимость) графа?

Задан 5 месяцев назад798 просмотров2 ответа

Не расстояния нужны, а просто для каждой пары (i, j) ответить: достижима ли j из i. n около 1000. Можно ли приспособить Флойда под это и ускорить?

Богдан Степанов 🥚 Яйцо

спросил 5 месяцев назад

2 ответа

✓ Принятый ответ — помог автору

Да, это транзитивное замыкание — Флойд по той же схеме, но вместо min суммы используем логическое ИЛИ: j достижима из i, если была достижима напрямую ИЛИ через k.

// reach[i][j] = true, если есть ребро i->j; reach[i][i] = true
for (int k = 0; k < n; k++)
    for (int i = 0; i < n; i++)
        if (reach[i][k])
            for (int j = 0; j < n; j++)
                reach[i][j] = reach[i][j] || reach[k][j];

Сложность O(V³). Обратите внимание на оптимизацию: проверку if (reach[i][k]) вынесли наружу внутреннего цикла — если k недостижима из i, нет смысла перебирать j.

Дарья Герасимова 🐣 Птенец

5 месяцев назад

Если n большое (несколько тысяч), используйте std::bitset — это ускоряет в 64 раза по константе. Храните каждую строку как bitset<N>, и обновление превращается в одну операцию ИЛИ над битсетами:

bitset<N> reach[N];
for (int k = 0; k < n; k++)
    for (int i = 0; i < n; i++)
        if (reach[i][k]) reach[i] |= reach[k];

Асимптотика формально та же O(V³/64), но на практике это разница между TLE и AC.

Иван Соловьёв 🐣 Птенец

4 месяца назад

Ваш ответ

Войдите, чтобы ответить на вопрос.