Привет.

На емаксе лежит вот такая реализация алгоритма поиска мостов:

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

Спасибо.