Семинар 4.

1.	Алгоритм Тарьяна нахождения компонент сильной связности.
	Во-первых вспомним, что если мы попали в компоненту сильной связности через
	вершину v (назовём такую вершину корневой вершиной её компоненты сильной
	связности), то после выхода из этой вершины, вся её компонента будет обойдена.
	Таким образом все вершины из той же компоненты сильной связности будут лежать
	в поддереве с корнем в v. Было бы здорово, если б мы умели как-то определять,
	что мы находимся именно в такой вершине. Тогда наш алгоритм будет работать так:
	заводим стек и когда в процессе обхода в глубину впервые заходим в вершину,
	кладём её в этот стек. Когда мы завершаем обработку какой-то вершины v, мы
	проверяем, является ли она первой обработанной из своей компоненты сильной
	связности. Если является, то мы вынимаем из стека все вершины вплоть до v и
	объявляем их одной компонентой. И это будет соответствовать действительности.
	Там будут все вершины из данной компоненты, так как все они потомки v, и там
	не будет ничего лишнего. Действительно, если встретилась вершина u из другой
	компоненты, то это значит, что она находится где-то в поддереве, начинающемся
	в v, вместе с вершиной w, через которую наш обход зашёл в эту компоненту (иначе,
	w предок v и существует цикл, содержащий w, v и u, то есть все они лежат в одной
	компоненте). А это значит, что вершину u мы вытащим из стека, когда закончим
	обработку вершины w.

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

3.	Докажем индукцией по времени окончания обработки следующее утверждение:
	(1) в стеке нет вершин из полностью чёрных компонент и (2) l[v] ⩾ d[r], где
	r — корень компоненты, содержащей v: r = root(v).
	(2)	Итак, l[v] = min(d[v], {l[u]}, {d[w]}).
		1.	Очевидно, d[v] ⩾ d[r].
		2.	Заметим, что f(u) < f(v). Если u ∈ SCC(v), то l[u] ⩾ d[root(u)] = d[r].
			Если u ∉ SCC(v), то u = root(u), значит по предположению (2):
			l[u] ⩾ d[u], а так как d[u] ⩾ d[v] ⩾ d[r], то l[u] ⩾ d[r].
		3.	w — в стеке, значит либо она сама серая, либо она чёрная, и тогда, по
			предположению (1) в стеке есть серая вершина t из той же компоненты.
			Значит, есть путь, начинающийся в v, проходящий через w, затем t и
			возвращающийся обратно в v (раз t серая, то она предок v по дереву
			обхода). Значит, w ∈ SCC(v), откуда d[w] ⩾ d[r].
		Таким образом мы получили (2): l[v] ⩾ d[r].
	(1)	По предположению индукции, перед тем как мы закончили обрабатывать v,
		в стеке есть только вершины из не полностью чёрных компонент. Когда мы
		обработали v, мы перекрашиваем в чёрный только её, значит полностью чёрная
		компонента у нас могла появиться только если v была последней необработанной
		вершиной этой компоненты, то есть она была её корневой вершиной. Таким
		образом, из (2) мы получаем, что l[v] ⩾ d[v], а значит l[v] = d[v]. Но
		именно при этом условии наш алгоритм начинает выкидывать вершины из стека,
		все, вплоть до v, а так как она корневая, то в стеке не останется ни одной
		вершины из SCC(v).
	Итак, мы доказали лемму, а с ней и важное следствие: если вершина v — корневая,
	то наш алгоритм выкинет из стека все вершины этой компоненты в момент окончания
	обработки v. Осталось доказать, что алгоритм не начнёт выкидывать вершины, если
	v — не корневая. То есть, что если l[v] = d[v], то v = root(v).

4.	Докажем индукцией по времени окончания обработки следующее утверждение:
	(1) если l[v] = d[v], то v = root(v), (2) от вершины стека до текущей вершины
	в стеке лежат только вершины из той же компоненты, и (3) вершина вынимается из
	стека только когда заканчивается обработка корня соответствующей компоненты.
	(1)	Пусть u = root(v) ≠ v. В момент обработки v, u — серая. На пути из v в u,
		найдём первую вершину t, не являющуюся потомком v в дереве обхода, а за w
		обозначим вершину, которая ей предшествует на этом пути. Ребро (w, t) —
		обратное (если t — серая) или перекрёстное (если t — чёрная), в любом
		случае d[t] < d[v]. И в обоих случаях t лежит в стеке. Если t серая, то
		она в стеке, так как выше текущей в стеке лежат только чёрные вершины,
		откуда следует, что из стека не вынимаются серые вершины. Если t чёрная,
		то она в стеке по предположению (3). Так как w потомок v в дереве обхода,
		то существует путь из v в w по рёбрам дерева, а значит l[v] ⩽ d[t] < d[v].
	(2)	Так как мы вынимаем из стека вершины от текущей до самого верха, то над
		текущей вершиной может лежать только один из её сыновей. Если он из другой
		компоненты, то он сам и всё что выше него должны были быть убраны в момент
		окончания его обработки. Значит он из той же компоненты, что и текущая
		вершина. А всё что выше него из той же компоненты по предположению индукции.
	(3)	Пусть обработав вершину v мы решили, что пора вынимать вершины из стека.
		Тогда во-первых, из (2) следует, что выше по стеку будут лежать только
		вершины из SCC(v), так что вершины из других компонент мы не вытащим, а
		во-вторых, из (1) следует, что v — корень SCC(v), то есть наш алгоритм
		работает ровно так как мы хотели, и, в частности, выполняется (3).
	Мы, наконец, доказали, что алгоритм работает правильно.