-
Notifications
You must be signed in to change notification settings - Fork 0
/
euler_path_cycle.cpp
95 lines (89 loc) · 2.36 KB
/
euler_path_cycle.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
using SetGraph = vector<multiset<int>>;
vector<int> GetEulerCycle(SetGraph g) {
for (size_t i = 0; i < g.size(); ++i) {
if (g[i].size() % 2) {
return {};
}
}
vector<int> ans;
stack<int> dfs;
dfs.push(0);
while (!dfs.empty()) {
int cur = dfs.top();
if (g[cur].empty()) {
dfs.pop();
ans.push_back(cur);
} else {
int nxt = *g[cur].begin();
g[cur].erase(g[cur].find(nxt));
g[nxt].erase(g[nxt].find(cur));
dfs.push(nxt);
}
}
return ans;
}
vector<int> GetEulerCycleOriented(SetGraph g) {
vector<size_t> incoming(g.size(), 0);
for (size_t i = 0; i < g.size(); ++i) {
for (int nxt : g[i]) {
++incoming[nxt];
}
}
for (size_t i = 0; i < g.size(); ++i) {
if (incoming[i] != g[i].size()) {
return {};
}
}
vector<int> ans;
stack<int> dfs;
dfs.push(0);
while (!dfs.empty()) {
int cur = dfs.top();
if (g[cur].empty()) {
dfs.pop();
ans.push_back(cur);
} else {
int nxt = *g[cur].begin();
g[cur].erase(g[cur].find(nxt));
dfs.push(nxt);
}
}
std::reverse(ans.begin(), ans.end());
return ans;
}
vector<int> GetEulerPathOriented(SetGraph g) {
vector<size_t> incoming(g.size(), 0);
for (size_t i = 0; i < g.size(); ++i) {
for (int nxt : g[i]) {
++incoming[nxt];
}
}
int start = -1, finish = -1;
for (size_t i = 0; i < g.size(); ++i) {
if (incoming[i] != g[i].size()) {
if (incoming[i] < g[i].size() && start == -1) {
start = static_cast<int>(i);
} else if (incoming[i] > g[i].size() && finish == -1) {
finish = static_cast<int>(i);
} else {
return {};
}
}
}
if (start == -1 || finish == -1) {
return {};
}
g[finish].insert(start);
vector<int> cycle = GetEulerCycleOriented(g);
if (cycle.empty()) {
return {};
}
cycle.pop_back();
for (size_t i = 1; i < cycle.size(); ++i) {
if (cycle[i - 1] == finish && cycle[i] == start) {
std::rotate(cycle.begin(), cycle.begin() + i, cycle.end());
break;
}
}
return cycle;
}