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

Автор AlexanderBolshakov, 12 лет назад, По-русски

Предисловие

Пишу с надеждой, что есть те, кто этот алгоритм не знают, но он им может пригодиться :). В-общем, утром 16 июня я открыл задачи с NEERC 2010 и остановился на C-шке (Cactus Revolution), в которой нужно было разрезать кактус так, чтобы у нас получилось сколько-то равных связных частей, или сказать, что это сделать невозможно. Мне быстро пришла в голову идея, что нужно этот кактус как-то подвесить на манер дерева, и после этого решать задачу по аналогии с задачей о разрезании дерева. Вначале были идеи о конденсации простых циклов, введении псевдовершин и т.п. Но вскоре пришла та самая идея, о которой я и хочу рассказать в этом топике.

Идея

Мысленно выполним "раздваивание" всех мостов, вот что получится с графом из примера:

Теперь каждая вершина лежит на цикле. Заметим, что любые два цикла имеют максимум одну общую вершину (доказывается через определение кактуса). Мысленно сожмем все циклы в одну вершину и проведем ребра между смежными циклами. В этом графе могут быть циклы, но при этом все они являются частью какой-то клики. Теперь мы можем мысленно выполнить DFS по этому графу, и при попадании в вершину клики, разомкнуть эту клику, удалив все ее ребра кроме ведущих в вершину, в которую мы зашли первой. Теперь у нас получилось дерево. Мысленно подвесим это дерево за ту же вершину, через которую мы выполняли первый DFS и получим между смежными циклами отношение "предок-потомок". Но как мы будем это все хранить? А очень просто: разомкнем каждый цикл путем выкидывания из него вершины, входящей кроме этого цикла также и в его предок, а в список потомков этой вершины добавим массив, содержащий разомкнутый цикл. Вот изображение той структуры, которую мы получим в конечном итоге, если подвесим кактус из примера за вершину 1 (извиняюсь за качество — рисовал в MSPaint'е):

Реализация (на Java)

На практике все можно реализовать при помощи одного DFS'а, без предварительного сжатия циклов, построения графа их смежности и т.п. Алгоритм в целом такой: мы ищем мосты и циклы. Когда мы находим цикл, мы записываем по порядку все его вершины (кроме одной — той, которая будет как бы его корнем) в массив и добавляем этот массив в список потомков этого самого "как бы корня". С мостами же очевидно, что они ни на каких циклах не лежат, поэтому после спуска по мосту (v, e) из вершины v мы просто добавляем массив из одной вершины e в список потомков v.

int n;
ArrayList<Integer>[] graph;
ArrayList<int[]>[] cactus;

int[] stack;
int cnt = 0;
int[] color;

int[] tin;
int[] tchild;
int curtime = 0;

void hang(int v, int prev) {
	color[v] = 1;
	tin[v] = tchild[v] = curtime++;
	stack[cnt++] = v;
	for (int e : graph[v]) {
		if (color[e] == 1 && e != prev) {
			tchild[v] = min(tchild[v], tin[e]);
			int start = cnt - 1;
			while (stack[start - 1] != e) {
				start--;
			}
			int[] cycle = new int[cnt - start];
			for (int i = 0; i < cycle.length; i++) {
				cycle[i] = stack[start + i];
			}
			cactus[e].add(cycle);
		} else if (color[e] == 0) {
			hang(e, v);
			tchild[v] = min(tchild[v], tchild[e]);
			if (tchild[e] > tin[v]) {
				cactus[v].add(new int[] { e });
			}
		}
	}
	cnt--;
	color[v] = 2;
}

void solve() throws Exception {
	/*
	 * Инициализируем массивы, считываем граф и т.п.
	 */
	
	hang(0, -1);
	
	/*
	 * Решаем задачу
	 */
}

Послесловие

Мне было бы интересно узнать две вещи:
1. Боян или нет?
2. Как решала задачу, ради которой я придумал этот алгоритм, команда ИТМО 2?

UPD. Ах да, вот полный код моего решения задачи (тестировал при помощи архива жюри).
UPD2. Поправил объяснение на свежую голову, надеюсь, что стало чуть более понятным.

UPD3. Вопрос: кто минусуют пост и при этом никак его не комментируют? Те, для кого это уже боян или те, кто ничего не поняли?

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

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

"Очевидно, полученный граф смежности циклов является деревом"

А почему? Разве если три цикла пересекаются по одной вершине, то они не будут образовывать цикл?(Они же все друг другу смежные). Или я что-то неправильно понял?

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится

    Тогда это будет не кактус.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Какой именно граф Вы имеете в виду? Если такой, в котором три простых цикла имеют одну общую вершину, то в нем один цикл будет родителем, а два других — его прямыми потомками. А если Вы имеете в виду граф, в котором три простых цикла попарно пересекаются, при этом хотя бы две точки пересечения различны — это явно не кактус, т.к. в нем простых циклов больше трех.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      Ну я просто посмотрел на картинку, где ребра раздвоены, подумал, что раздвоены они, наверное, ровно для того, чтобы можно было считать их циклами, а на картинке как раз три цикла(два из которых, на самом деле, из одного ребра) пересекаются по вершине.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Я, на самом деле, вполне могу не знать определение кактуса (если не ошибаюсь, то должно быть единственное условие, что все ребра лежат, как максимум в одном простом цикле?). Так вот, если разрешено пересекаться по вершине и именно это является признаком смежности двух циклов, то получается всё-таки не дерево? Извините, если я вдруг как-то слишком формально пытаюсь придраться к простой идее. Но меня это почему-то не оставляет равнодушным :)

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Да, Вы правы, я описал этот момент неправильно, по моему описанию там действительно получается цикл. Сейчас, соберусь с мыслями и все поправлю.

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        Вообще кактусы (также как и компоненты двусвязности) бывают вершинные и реберные. У тебя в посте описан реберный. Да, в задаче вроде тоже реберный :)