
	\Section{Топологическая сортировка и т.п.}{9 ноября 2015г. }{Плющ}
		\Subsection{Что хотим?}
				
			Дан ориентированный граф. Хотим найти такую перестановку вершин, что любое ребро идёт "слева направо". Она и называется топологической сортировкой.
				
			Сразу заметим, что если в графе есть цикл, то топологической сортировки не существует. Пусть у нас цикл v -> u ---> v (ребро v -> u, какой-то путь u ---> v). 
			
			Пусть правильный порядок - это ... v ... u ... Но все рёбра пути u ---> v должны идти слева направо, то есть правильный порядок - это ... u ... v ... Но есть ребро v -> u, значит, правильный порядок - это всё-таки ... v ... u ...
			
			В общем, в любом случае противоречие, так что в графе с циклами топологической сортировки действительно нет.

		\Subsection{Наивный алгоритм ($\Theta(n^2)$)}

			Давайте как-нибудь научимся искать топологическую сортировку. Сделаем n итераций, на каждой выберём вершину с входящей степенью 0 (степень, разумеется, считаем по вершинам, ещё не добавленным в  топологическую сортировку), добавляем её в топологическую сортировку. Если есть несколько вершин входящей степени 0, то можем выбрать ту, которая нам нужна, может быть, по условию (например, с минимальным номером, или, опять же,по критерию, указанному в условии задачи). Вершину входящей степени 0 мы берём просто потому, что все вершины, которые будут идти позже выбранной, не имеют рёбер в выбранную (просто потому, что в выбранную вообще сейчас нет рёбер).
			 \begin{code}
for (int it = 0; it < n; it++)
{
		int best = inf;
		for (int j = 0; j < n; j++)
			if (!deg_in[j] && (best == inf || our_comporator))
				best = j;
		for (int j = 0; j < n; j++)
			deg_in[j] -= e[best][j]; //e[i][j] is a number of edges from i to j
		cout << best << "\n";
		deg_in[best] = inf;							
}
			 \end{code}
		\Subsection{Более быстрый алгоритм нахождения топологической сортировки ($\Theta(n + m)$)}
		
			Заметим, что для любой вершины все её соседи идут позже в топологической сортировке. Получаем алгоритм
			\begin{code}
void dfs(int v)
{
	used[v] = 1
	for (int u : e[v])
		if (!used[u])
			dfs(u);
	topsort.push_front(v); 
	// or push_back and reverse(topsort.begin(), topsort.end()); after dfs
}	
			\end{code}
	 
		\Subsection{Проверка на наличие циклов}

			Пусть не гарантируется, что граф ацикличен. Научимся одним dfs'ом проверять наличие циклов и строить топологическую сортировку.
			\begin{code}
bool dfs(int v)
{
	used[v] = 1
	for (int u : e[v])
		if (!used[u])
			dfs(u)
		else
			if (used[u] == 1)
				return 0			
	topsort.push_front(v)
	used[v] = 2
}	
			\end{code}
			
			Красим вершины в 3 цвета: 0 - ещё не заходили (белый), 1 - уже зашли, но не вышли (серый), 2 - уже вышли (чёрный). Тогда понятно, что цикл есть, если мы из серой вершины попали в серую. dfs возвращает bool - правда ли, что граф ацикличен.	

		\Subsection{Топологическая сортировка и динамическое программирование}
		
			Пусть мы хотим найти количество путей из start в end. Понятно, что задача решается динамическим программированием. Также понятно, что правильный порядок обхода состояний - это топологическая сортировка (или её развёрнутый порядок).
			
			\Subsubsection{DP}
				\begin{code}
cnt[end] = 1;
for (int i = n; i >= 1; i--)
{
	v = topsort[i];
	for (int u : e[v])
		cnt[v] += cnt[u]
}
				\end{code}						
															\Subsubsection{Lazy DP}
				\begin{code}
fill(cnt, cnt + n, -1);
cnt[end] = 1;
int dfs(int v)
{
	if (cnt[v] != -1)
		return cnt[v];
	cnt[u] = 0;
	for (int u : e[v])
		cnt[v] += dfs(u)
	return cnt[v];			
}
				\end{code}			
	\Subsection{Сильная связность}
		
		Ориентированный граф сильно связен, если между любой (упорядоченной) парой вершин есть путь.
				
	\Subsection{Алгоритм нахождения компонент сильной связности}
		
		1. Запустим поиск топологической сортировки, игнорируя то, что её может и не существовать.
		
		2. Будем красить по обратным рёрбам. То есть берём непокрашенную вершину, красим её и всё, что из неё достижимо по обратным рёбрам (в новый цвет).
			\begin{code}
void dfs(int v)
{
	clr[v] = color;
	for (int u : ee[v])
		if (!clr[u])
			dfs(u);
}
color = 0;
for (int i = 1; i <= n; i++)
	if (!clr[topsort[i]])
	{
		color++;
		dfs(topsort[i]);
	}
			\end{code}	
	\Subsection{Почему работает?}		
		
		Давайте поддерживать инвариант: 
		
		а: все вершины v, для которых scc(v) = scc(j) (j < i) уже покрашены до того, как мы начали работать с i-той вершиной в порядке топологической сортировки.

		b: Никакая u: $\forall$ j < i: scc(u) != scc(j) не покрашена.
		
		Смотрим на i-тую вершину в порядке топологической сортировки (для удобства называть её тоже будем i). Если i не покрашена, то вся scc(i) достижима из i по обратным рёбрам. Покрасим scc(i). Покажем, что лишние вершины не будут покрашены.
		
		От противного: $\exists$ x, покрашенная из i, но scc(x) != scc(i). 
		
		Смотрим на scc(x). Пусть y - вершина, в которую мы зашли первым dfs'ом (тем, который собирает topsort) раньше всего. Покажем, что y в topsort раньше, чем scc(i). Вошли первым dfs'ом в y. scc(i) либо целиком чёрная, либо целиком белая. Если scc(i) целиком серая, то из scc(i) есть путь в y, которая находится в scc(x), из которой есть путь в scc(i). Получаем противоречие. Частичные цвета тоже невозможны, т.к. компоненты мы красим сразу и целиком.
		
		Пусть scc(i) вся чёрная => в топологической сортировке y будет раньше => y уже посещён, а значит, scc(y) уже покрашена.
		
		Пусть  scc(i) вся белая => есть путь из y в scc(i), поэтому scc(i) станет чёрной раньше, чем y => в топологической сортировке y идёт раньше, чем scc(i).
		
		В любом случае имеем противоречие (с инвариантом и в целом с ситуацией, которую мы рассматриваем).
				