-
Notifications
You must be signed in to change notification settings - Fork 2
/
topological_sort.cpp
58 lines (50 loc) · 1.15 KB
/
topological_sort.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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// For directed acyclic graphs only
// It has atleast 1 vertex with indegree 0 and 1 with outdegree 0
// TC: O(E+V)
///////////////////// start yanking ////////////////////
vector<vector<ll>> graph;
vector<bool> visited;
void build(ll n) { // call me (precomputation)
graph.resize(n+1);
visited.resize(n+1);
}
void insert_edge(ll s, ll d) { // call me (building)
graph[s].push_back(d);
}
void dfs(stack<ll> &s, ll v) {
visited[v] = true;
for (auto &i : graph[v]) {
if (!visited[i]) {
dfs(s, i);
}
}
s.push(v);
}
void topo_sort() { // call me (result)
stack<ll> s;
for (ll i = 1; i < graph.size(); i++) {
if (!visited[i]) {
dfs(s, i);
}
}
while (!s.empty()) {
cout << s.top() << " ";
s.pop();
}
}
///////////////////// stop yanking /////////////////////
int main() {
ll v, e, s, d;
cin >> v;
build(v); // called
cin >> e;
for (ll i = 0; i < e; i++) {
cin >> s >> d;
insert_edge(s, d); // called
}
topo_sort(); // called
return 0;
}