Топологическая сортировка (Topological sort)

Часто встречаемый алгоритм в задачах на графы. Как правило, он является лишь вспомогательным, но это не уменьшает его значимости. Поэтому ему можно смело дать Оскара за лучшую мужскую роль второго плана.

Есть ряд очень качественных публикаций на эту тему:
1) e-maxx
2) habrahabr
3) rain.ifmo.ru

Рассмотрим три задачи на эту тематику:

1) 1022(timus) Генеалогическое дерево 
Входные данные можно представить в следующем виде:

Однако тот же самый граф можно представить в другом виде:

Как можно заметить - все стрелки смотрят вправо, следовательно нужный порядок найден. В данной задаче гарантируется, что нет циклов. Это несколько упрощает задачу. Основной код программы изложен ниже: 

1. int n;
2. enum TYPE_VERTEX{WHITE,GRAY,BLACK};
3. vector<vector<int> > adj;
4. vector<TYPE_VERTEX> used;
5. ...
6. void dfs(int cur, vector<int> &ans) {
7.   used[cur] = GRAY;
8.   for (int i=0; i<adj[cur].size(); i++) {
9.     int next = adj[cur][i];
10.     // if (used[next] == GRAY) // Circle
11.     if (used[next] == WHITE)
12.       dfs(next,ans);
13.   }
14.   used[cur] = BLACK;
15.   ans.push_back(cur);
16. }
17. void topological_sort(vector<int> &ans) {
18.   for (int i=0;i<n;i++) {
19.     if (used[i] == WHITE) {
20.       dfs(i,ans);
21.     }
22.   }
23. }

* This source code was highlighted with Source Code Highlighter.

Полное решение задачи 1022(timus): здесь

2) 138(contester.tsure.ru) Квадраты из неравенств 
Задача выглядит угрожающе. Можно сразу догадаться, что всю эту таблицу нужно представить в виде графа(тестовый пример)

Логично предположить, что следующим нашим шагом будет топологическая сортировка полученного графа. При этом последовательность вершин получится в порядке возрастания. Т.е. сначала идут листья, которые не ссылаются на другие вершины, а на последнем месте – вершина, на которую не ссылается ни одна вершина:

Как видим все стрелки направлены влево, значит мы сделали все правильно. Следующее, что мы должны сделать – это определить численные значения всех 9 переменных. Для этого можем рассмотреть упрощенную задачу. Представим, что изначально наш граф состоял только из вершин B,D,A. Тогда чисто интуитивно можно присвоить B = 1, D = 2, A = 3. Если же обобщить на произвольный граф, то можно руководствоваться правилом, что численное представленное вершины равно количеству топологически меньших вершин + 1, т.е. количеству вершин левее рассматриваемой вершины в упорядоченном списке + 1. Из этих соображений получаем один из ответов на поставленную задачу:

Также не забываем грамотно обработать случай, когда граф имеет циклы.

Полный исходник на задачу 138(constester.tsure.ru): здесь (не тестировался, т.к. сервак висел во время написания поста).

3) 14F [Меньшиков]
Эта задача, демонстрирует, как можно применить топологическую сортировку в более сложной задаче. По своей сути решение данной подзадачи мало чем отличается от первой разобранной задачи(timus-1022)