-
Notifications
You must be signed in to change notification settings - Fork 2
/
topologicalSort.cpp
100 lines (90 loc) · 2.37 KB
/
topologicalSort.cpp
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
CLion
/* Troyan-Golovyan Vladislav*/
/* Contest 1, Task B*/
#include <iostream>
#include <vector>
#include <functional>
/* DFS */
void dfs (
const std::vector< std::vector<size_t> > &graph,
std::vector <char> &colors,
size_t v,
const std::function < void(size_t) > &in_callback,
const std::function < void(size_t) > &out_callback,
const std::function < bool(size_t) > &call_dfs_checker
) {
colors[v] = 1;
in_callback(v);
for (size_t i = 0; i < graph[v].size(); ++i) {
if (call_dfs_checker(graph[v][i])) {
dfs(graph, colors, graph[v][i], in_callback, out_callback, call_dfs_checker);
}
}
out_callback(v);
colors[v] = 2;
}
/* Topological sort */
bool top_sort (const std::vector<std::vector<size_t>> &graph, std::vector<size_t> &sort_result) {
std::vector<char> colors(graph.size(), 0);
sort_result.clear();
bool res = true;
for (size_t i = 0; i < graph.size() && res; ++i) {
if (colors[i] == 0) {
dfs(
graph,
colors,
i,
[&] (size_t v) {
},
[&] (size_t v) {
sort_result.push_back(v);
},
[&] (size_t v) -> bool {
if (colors[v] == 1) {
res = false;
}
return colors[v] == 0;
}
);
}
}
return res;
}
/* Get input */
void get_input (
size_t &n,
size_t &m,
std::vector< std::vector<size_t> > &graph
) {
std::cin >> n >> m;
graph.assign(n, std::vector <size_t> ());
for (size_t i = 0; i < m; ++i) {
size_t a, b;
std::cin >> a >> b;
graph[a].push_back(b);
}
}
/* Set output */
void set_output (
const bool res,
std::vector <size_t> sort_result
) {
if (res) {
std::cout << "YES" << std::endl;
for (size_t i = 0; i < sort_result.size(); ++i) {
std::cout << sort_result[sort_result.size() - i - 1] << " ";
}
} else {
std::cout << "NO";
}
}
/* Main function */
int main() {
size_t n, m;
std::vector< std::vector<size_t> > graph;
get_input(n, m, graph);
std::vector <size_t> sort_result;
bool res = top_sort(graph, sort_result);
set_output(res, sort_result);
return 0;
}