forked from MaskRay/LeetCode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
reconstruct-itinerary.cc
50 lines (47 loc) · 1.11 KB
/
reconstruct-itinerary.cc
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
// Reconstruct Itinerary
/// Hierholzer's algorithm
class Solution {
unordered_map<string, multiset<string>> m;
vector<string> ret;
void hierholzer(string x) {
while (! m[x].empty()) {
string y = *m[x].begin();
m[x].erase(m[x].begin());
hierholzer(y);
}
ret.push_back(x);
}
public:
vector<string> findItinerary(vector<pair<string, string>> tickets) {
for (auto &x: tickets)
m[x.first].insert(x.second);
hierholzer("JFK");
reverse(ret.begin(), ret.end());
return ret;
}
};
/// non-recursive Hierholzer's algorithm
class Solution {
public:
vector<string> findItinerary(vector<pair<string, string>> tickets) {
unordered_map<string, multiset<string>> m;
for (auto &x: tickets)
m[x.first].insert(x.second);
stack<string> st;
vector<string> ret;
st.push("JFK");
while (! st.empty()) {
auto &x = st.top();
if (m[x].empty()) {
ret.push_back(x);
st.pop();
} else {
auto it = m[x].begin();
st.push(*it);
m[x].erase(it);
}
}
reverse(ret.begin(), ret.end());
return ret;
}
};