Привет.
На емаксе лежит вот такая реализация алгоритма поиска мостов:
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] будет не готов, но всё же. Какой тест завалит реализацию с таким единственным изменением? Пробовал погонять на своих тестах -- вроде отрабатывает.
Спасибо.