Привет.
На емаксе лежит вот такая реализация алгоритма поиска мостов:
void dfs (int v, int p = -1) {
used[v] = true;
tin[v] = fup[v] = timer++;
for (size_t i=0; i<g[v].size(); ++i) {
int to = g[v][i];
if (to == p) continue;
if (used[to])
fup[v] = min (fup[v], tin[to]);
else {
dfs (to, v);
fup[v] = min (fup[v], fup[to]);
if (fup[to] > tin[v])
IS_BRIDGE(v,to);
}
}
}
Вопрос: а что если, когда попытаемся пройти по обратному ребру, в строчке 8 мы обновим fup[v] следующим образом:
fup[v] = min (fup[v], fup[to]) ?
Вроде интуитивно понятно, что все смежные вершины to могли еще быть не посещены поиском в глубину и fup[to] будет не готов, но всё же. Какой тест завалит реализацию с таким единственным изменением? Пробовал погонять на своих тестах -- вроде отрабатывает.
Спасибо.
всегда так и делаю, пока не валилось.
strange :\
а почему? во-первых tin>=fup, во вторых, раз зашли в этот if, то это цикл и нет смысла проверять на мост.
а, ну вообще логично, да.
Код со строчкой fup[v] = min (fup[v], fup[to]) работает, и он правильный.
Почему? Понятно, что fup[to] <= tin[to]. Кроме того, tin[to] меньше чем tin[p], где p — предок текущей вершины (иначе мы пришли бы из другого предка). Поэтому, если для вершины v удалось установить fup[v] в tin[to] (или меньше), то ребро из p в v уже не будет мостом. Если удастся установить fup[v] = fup[to] <= tin[to], то это же ребро опять же не будет мостом, что верно.
Вот когда ищешь точки сочленения, там похожий алгоритм, но эту строчку важно писать именно так: fup[v] = min (fup[v], tin[to]). Поэтому возможно имеет смысл писать везде одинаково.
Прояснилось, спасибо.
Операция
fup[v] = min (fup[v], tin[to]);
выполняется только если used[to] — true, то dfs уже был вызван для вершины to. Это значит, что fup[to] наверняка "готов".Лично я полагаю, что изменённый алгоритм корректен.
UPD:
Упс, не знал, что при просмотре codeforces на английском русские комментарии не отображаются. Думал, я пишу первый
А реализация нахождения точек сочленения на емаксе вот такая:
Вот почему-то если тут заменить 9 строку на
fup[v] = min (fup[v], fup[to])
, то падает на 55 тесте в одной учебной задаче (находится в закрытой группе).Кто-нибудь может привести пример, когда это работает неправильно? Почему там нужно сравнивать именно с tin[to]?