Блог пользователя 1k_trash

Поиск мостов -- помогите найти тест, который завалит вот такую реализацию
Автор 1k_trash, 10 лет назад, По-русски

Привет.

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

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

Спасибо.

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

всегда так и делаю, пока не валилось.

→ Ответить
»
10 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Код со строчкой 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]). Поэтому возможно имеет смысл писать везде одинаково.

→ Ответить
»
8 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Операция fup[v] = min (fup[v], tin[to]); выполняется только если used[to] — true, то dfs уже был вызван для вершины to. Это значит, что fup[to] наверняка "готов".

Лично я полагаю, что изменённый алгоритм корректен.

UPD:

Упс, не знал, что при просмотре codeforces на английском русские комментарии не отображаются. Думал, я пишу первый

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

А реализация нахождения точек сочленения на емаксе вот такая:

void dfs (int v, int p = -1) {
	used[v] = true;
	tin[v] = fup[v] = timer++;
	int children = 0;
	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] && p != -1)
				IS_CUTPOINT(v);
			++children;
		}
	}
	if (p == -1 && children > 1)
		IS_CUTPOINT(v);
}

Вот почему-то если тут заменить 9 строку на fup[v] = min (fup[v], fup[to]), то падает на 55 тесте в одной учебной задаче (находится в закрытой группе).

Кто-нибудь может привести пример, когда это работает неправильно? Почему там нужно сравнивать именно с tin[to]?

→ Ответить