#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
vector<set<int>> g(n);
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
a--; b--;
g[a].insert(b);
g[b].insert(a);
}
//dont need to check if possible bc question says is possible
vector<int> seq;
stack<int> stak;
stak.push(0);
while (!stak.empty()) {
int u = stak.top();
//~ cout << u+1 << endl;
if (g[u].size() > 0) { //if still neighbours
int v = *g[u].begin();
stak.push(v);
g[u].erase(v); //erase edge from both sides
g[v].erase(u);
} else { //need to add to tour
stak.pop();
seq.push_back(u);
//~ cout << u+1 << " ";
}
}
//~ cout << "seq " ;
//~ for (int i : seq) {
//~ cout << i+1 << " ";
//~ }
//~ cout << endl;
//now make sure no vertices visited multiple times
map<int, int> index;
vector<pair<int, int>> groups; //end then start, should have soonest end points first
for (int i = 0; i < seq.size(); i++) {
int a = seq[i];
if (index[a] != 0) { //used before
groups.push_back({i+1, index[a]});
index[a] = 0;
} else {
index[a] = i+1; //so no confusion if in first position
}
}
int lb = n; //leftmost which has been done
int rb = 0; //rightmost which has been done
for (auto x : groups) {
if (x.first < lb || x.second > rb || (x.second < lb && x.first > rb)) { //if no overlap --> if on left, if on right, if around
for (int i = x.second-1; i < x.first-1; i++) { //iterate over all spots
if (i < lb || i >= rb) { //so knot only appears once, and subroutes arent a part
cout << seq[i]+1 << " ";
}
}
cout << endl;
lb = x.second-1;
rb = x.first-1;
}
}
}
//TL really soon
Compilation message
postmen.cpp: In function 'int main()':
postmen.cpp:47:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for (int i = 0; i < seq.size(); i++) {
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
600 KB |
Same junction appears twice in a route |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Same junction appears twice in a route |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Same junction appears twice in a route |
| 3 |
Halted |
0 ms |
0 KB |
- |
