Условие:
Дан ориентированный невзвешенный граф. Необходимо топологически отсортировать его вершины.
Входные данные
В первой строке содержатся количество вершин [latex]n[/latex] (1 ≤ [latex]n[/latex] ≤ 100000) и количество рёбер [latex]m[/latex] (1 ≤[latex]m[/latex] ≤ 100000) в графе. В следующих [latex]m[/latex] строках перечислены рёбра графа, каждое из которых задаётся парой чисел — номерами начальной и конечной вершины.
Выходные данные
Вывести любую топологическую сортировку графа в виде последовательности номеров вершин. Если граф невозможно топологически отсортировать, то вывести -1.
Тесты:
| Входные данные | Выходные данные |
| 6 6 1 2 3 2 4 2 2 5 6 5 4 6 |
4 6 3 1 2 5 |
| 2 2 1 2 2 1 |
-1 |
| 4 5 1 2 1 3 3 4 2 4 1 4 |
1 3 2 4 |
| 4 5 1 2 1 3 3 4 2 4 4 1 |
-1 |
Решение:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
#include <iostream> #include <vector> #include <algorithm> using namespace std; bool cyclic (int v, int &cycle_st, vector <int> *graph, vector <int> &color ) { //проверка графа на цикличность color[v] = 1; for (size_t i = 0; i < graph[v].size(); ++i) { int to = graph[v][i]; if (color[to] == 0) { //если в вершину не входили ни разу if (cyclic (to, cycle_st, graph, color)) return true; } else if (color[to] == 1) { //если в указанную вершину ранее входили, то значит, что найден цикл cycle_st = to; // и меняем значение индикатора return true; } } color[v] = 2; //указываем, что в вершину больше ни разу входить не будем return false; } void dfs (int v, vector <int> *graph, vector<bool> &used, vector <int> &answer) { used[v] = true; //указываем, что использовали данную вершину for (int i=0; i < graph[v].size(); i++) { int to = graph[v][i]; //по списку проходим по всем вершинам, к которым можно пройти от вершины v if (!used[to])//и если вершину не рассматривали, то применяем алгоритм поиска в глубину для неё dfs (to, graph, used, answer); } answer.push_back (v+1); // заносим вершину в вектор, хранящий результат } void topological_sort(int n, vector <int> *graph, vector<bool> &used, vector <int> &answer) { for (int i = 0; i < n; i++) //указываем, что ни одна вершина не была использована used[i] = false; for (int i = 0; i < n; i++) if (!used[i]) //если в ходе предыдущий операций вершина не использовалась dfs (i, graph, used, answer); // то вызываем для неё алгоритм поиска в глубину reverse (answer.begin(), answer.end()); } int main() { int n, m; // число вершин и ребер cin >> n >> m; int a, b; vector <int> graph[100001]; // граф vector <bool> used (n); vector<int> answer; vector<int> color (n,0); //массив, хранящий кол-во посещений для данной вершины. int cycle_st = -1; for (int i = 0; i < m; i++){ cin >> a >> b; graph[a-1].push_back(b-1); } for (int i = 0; i < n; i++){ if (cyclic(i, cycle_st, graph, color)) //проверка графа на ацикличность break; } if (cycle_st != -1){ cout << "-1"; } else{ topological_sort(n, graph, used, answer); for (int i = 0; i < answer.size(); i++) { cout << answer[i] << " "; } cout << endl; } return 0; } |
Описание решения:
Для решения данной задачи необходимо было воспользоваться алгоритмом топологической сортировки, посредством поиcка в глубину. Чтобы применить данный алгоритм, необходимо было проверить граф на ацикличность с помощью алгоритма поиска в глубину. Это было реализовано функцией [latex]cyclic[/latex], которая проходила по всему графу в поиске цикла. Если цикл был найден, то функция меняла значение переменной [latex]cycle_st[/latex]. Далее, если цикл был найден, то программа выводить -1, иначе применяется алгоритм топологической сортировки, реализованный в двух функциях:
|
20 |
void dfs (int v, vector <int> *graph, vector<bool> &used, vector <int> &answer) |
и
|
30 |
void topological_sort(int n, vector <int> *graph, vector<bool> &used, vector <int> &answer) |
После выполнения этих функций был получен топологически отсортированный список вершин, но в обратном порядке. Поэтому разворачиваем его с помощью функции [latex]reverse[/latex] .
Засчитанное решение на e-olymp.com.
Код решения на ideone.com.