Предисловие

Пишу с надеждой, что есть те, кто этот алгоритм не знают, но он им может пригодиться :). В-общем, утром 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. Вопрос: кто минусуют пост и при этом никак его не комментируют? Те, для кого это уже боян или те, кто ничего не поняли?