Семинар 3.

1.	На прошлом семинаре были рассказаны алгоритмы нахождения компонент сильной
	связности и рёберной двусвязности, работающие за линейное время и использующие
	два обхода в глубину. Сейчас мы рассмотрим алгоритмы, решающие те же задачи,
	но делающие это за один обход в глубину.

2.	Для этого, в каждой вершине мы будем писать два числа: d[v] — время обнаружения
	вершины v и l[v] — минимальное время обнаружения среди всех вершин которые
	могут быть достигнуты из поддерева с корнем в v при прохождении ровно по одному
	обратному ребру (и по скольки угодно рёбрам дерева). Последнее число считается
	в момент окончания обработки вершины по следующему рекуррентному соотношению:
		l[v] = min(l[u], d[w], d[v]),
	где u пробегает всех сыновей v по рёбрам дерева, а w — всех сыновей по обратным
	рёбрам. Это для неориентированного графа.

3.	Алгоритм нахождения мостов и компонент рёберной двусвязности.
	Заметим, что если у вершины v: d[v] = l[v], то ребро, по которому мы в неё
	пришли — мост (и все мосты имеют такой вид). Таким образом мы можем находить
	мосты за один обход в глубину. Чтобы ещё и выделить компоненты двусвязности,
	нужно каждый раз как только мы видим новую вершину, пихать её в стек.
	А как только мы обнаруживаем мост, вынимаем из стека все вершины вплоть до
	текущей — это и будет очередная компонента рёберной двусвязности.

4.	Алгоритм нахождения точек сочленения.
	Посмотрим на лес обхода в глубину. Корни деревьев будут точками сочленения
	титтк у них более одного сына (так как нет поперечных рёбер), а внутренняя
	вершина v будет точкой сочленения титтк у неё найдётся сын u, что l[u] ⩾ d[v].

5.	Компоненты вершинной двусвязности ищутся аналогично компонентам рёберной
	двусвязности, только в стек нужно записывать не вершины, а рёбра.
	Делаем обход в глубину. Как только видим непосещённого сына, кладём ребро
	до него в стек. Когда заканчиваем обрабатывать сына u, считаем его l[u] и
	сравниваем с временем обнаружения d[v]. Если l[u] ⩾ d[v]), то вытаскиваем
	из стека все рёбра вплоть до (v, u) — это и будет очередная компонента
	вершинной двусвязности. Заметим, что у каждой точки сочленения компонент
	вершинной двусвязности может быть несколько.