Задача взята отсюда.
Условие
Дан ориентированный невзвешенный граф. Необходимо его топологически отсортировать.
Входные данные
В первой строке содержатся два натуральных числа [latex]n[/latex] и [latex]m[/latex] ([latex]1 \leq n \leq 10^5[/latex], [latex]1 \leq m \leq 10^5[/latex]) — количество вершин и рёбер в графе соответственно. Далее в [latex]m[/latex] строках перечислены рёбра графа. Каждое ребро задаётся парой чисел — номерами начальной и конечной вершин соответственно.
Выходные данные
Вывести любую топологическую сортировку графа в виде последовательности номеров вершин. Если граф невозможно топологически отсортировать, требуется вывести [latex]-1[/latex].
Решение
Для решения использовался алгоритм топологической сортировки методом поиска в глубину (подробнее в комментариях к коду). Функция bool dfs() (поиск в глубину) также проверяет, цикличен ли граф, т.к. по условию он может как содержать, так и не содержать циклы. Результат сортировки заносим в вектор result, потом выводим его элементы по порядку.
Тесты
| № | Входные данные | Выходные данные |
| 1 | 6 6 1 2 3 2 4 2 2 5 6 5 4 6 |
4 6 3 1 2 5 |
| 2 | 3 3 1 2 2 3 3 1 |
-1 |
| 3 | 4 4 1 4 4 3 3 2 4 2 |
1 4 3 2 |
Код
|
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> #define WHITE 0 //вершина не посещена #define GREY 1 //вершина обрабатывается #define BLACK 2 //вершина обработана using namespace std; bool dfs (int v, vector<int>* vertex, int* state, vector<int> &result, int size) //возвращает true или false в зависимости от того, был ли найден цикл { state[v] = GREY; //отмечаем, что вершина в процессе обработки for (int i = 0; i < vertex[v].size(); i++) //для каждой вершины, в которую можно попасть из данной { int dest = vertex[v].at(i); if (state[dest] == WHITE) //если еще не посетили - запускаем поиск в глубину, возвращаем true, если далее был найден цикл { if (dfs(dest, vertex, state, result, size)) return true; } else if (state[dest] == GREY) //если из вершины можно попасть туда, где мы уже были при данном порядке обхода - найден цикл { return true; } } //если цикл не найден: state[v] = BLACK; //помечаем вершину как обработанную result.push_back(v+1); //помещаем ее номер (со сдвигом на 1, из-за разницы в нумерациях) в вектор-результат сортировки return false; } void topologicalSort(vector<int>* vertex, int* state, vector<int> &result, int size) { for (int i = 0; i < size; i++) //для каждой вершины графа { if (state[i] == WHITE) //если она еще не посещена { bool cyclic = dfs(i, vertex, state, result, size); //вызываем для нее поиск в глубину if (cyclic) //если нашли цикл, возвращаем единственное значение -1 (по условию) { result.clear(); result.push_back(-1); return; } } } reverse(result.begin(), result.end()); //вершины добавляются в вектор в порядке, противоположном топологической сортировке, так что нужно вызвать для вектора reverse() } int main() { ios::sync_with_stdio(false); int n, m; cin >> n >> m; vector<int> vertex[n]; //сам граф int state[n]; //массив состояний вершин vector<int> result; fill (state, state + n, WHITE); //изначально ни одна вершина не посещена for (int i = 0; i < n; i++) { int begin, end; cin >> begin >> end; vertex[begin-1].push_back(end-1); } topologicalSort(vertex, state, result, n); //сортируем граф for (int i = 0; i < result.size(); i++) cout << result.at(i) << " "; return 0; } |
Ссылки
Код на ideaone.
Засчитанное решение на e-olymp.
Наглядное объяснение топологической сортировки здесь.
Зачтено.
Ссылка на топологическую сортировку и комментарии воде многое проясняют, но где же Ваши описания решения?