#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<vector<pair<int, int>>> g;
vector<bool> seen;
vector<int> seq;
void dfs(int k) {
while (!g[k].empty()) {
if (seen[g[k].back().second] == 1) {
g[k].pop_back();
continue; // if edge has already been deleted
}
seen[g[k].back().second] = 1;
int a = g[k].back().first;
g[k].pop_back();
dfs(a);
}
seq.push_back(k);
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
g = vector<vector<pair<int, int>>> (n);
seen = vector<bool> (m, 0);
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
a--; b--;
g[a].push_back({b, i});
g[b].push_back({a, i});
}
//dont need to check if possible bc question says is possible
dfs(0);
//now make tours out of this tour
vector<vector<int>> ans;
vector<int> count(n, 0);
stack<int> s; //has verteces which we can remove as appropriate
for (int i : seq) {
if (count[i] > 0) {
ans.push_back({});
while (s.top() != i) {
count[s.top()]--;
ans[ans.size()-1].push_back(s.top());
s.pop();
}
ans[ans.size()-1].push_back(i);
} else {
count[i]++;
s.push(i);
}
}
if (s.size() > 1) {
ans.push_back({});
while (!s.empty()) {
ans[ans.size()-1].push_back(s.top());
s.pop();
}
}
for (auto i : ans) {
for (int j : i) {
cout << j+1 << " ";
}
cout << "\n";
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
860 KB |
Output is correct |
| 5 |
Correct |
1 ms |
604 KB |
Output is correct |
| 6 |
Correct |
2 ms |
860 KB |
Output is correct |
| 7 |
Correct |
5 ms |
2396 KB |
Output is correct |
| 8 |
Correct |
1 ms |
604 KB |
Output is correct |
| 9 |
Correct |
25 ms |
10980 KB |
Output is correct |
| 10 |
Correct |
2 ms |
600 KB |
Output is correct |
| 11 |
Correct |
2 ms |
600 KB |
Output is correct |
| 12 |
Correct |
27 ms |
11856 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
2 ms |
860 KB |
Output is correct |
| 5 |
Correct |
1 ms |
604 KB |
Output is correct |
| 6 |
Correct |
1 ms |
860 KB |
Output is correct |
| 7 |
Correct |
5 ms |
2368 KB |
Output is correct |
| 8 |
Correct |
1 ms |
600 KB |
Output is correct |
| 9 |
Correct |
24 ms |
11236 KB |
Output is correct |
| 10 |
Correct |
1 ms |
600 KB |
Output is correct |
| 11 |
Correct |
2 ms |
604 KB |
Output is correct |
| 12 |
Correct |
28 ms |
11728 KB |
Output is correct |
| 13 |
Correct |
41 ms |
17284 KB |
Output is correct |
| 14 |
Correct |
39 ms |
13008 KB |
Output is correct |
| 15 |
Correct |
42 ms |
15872 KB |
Output is correct |
| 16 |
Correct |
39 ms |
17224 KB |
Output is correct |
| 17 |
Correct |
56 ms |
11384 KB |
Output is correct |
| 18 |
Correct |
61 ms |
14792 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
352 KB |
Output is correct |
| 3 |
Correct |
0 ms |
360 KB |
Output is correct |
| 4 |
Correct |
2 ms |
860 KB |
Output is correct |
| 5 |
Correct |
1 ms |
604 KB |
Output is correct |
| 6 |
Correct |
1 ms |
860 KB |
Output is correct |
| 7 |
Correct |
4 ms |
2368 KB |
Output is correct |
| 8 |
Correct |
1 ms |
604 KB |
Output is correct |
| 9 |
Correct |
38 ms |
10968 KB |
Output is correct |
| 10 |
Correct |
2 ms |
600 KB |
Output is correct |
| 11 |
Correct |
1 ms |
604 KB |
Output is correct |
| 12 |
Correct |
35 ms |
11728 KB |
Output is correct |
| 13 |
Correct |
50 ms |
17216 KB |
Output is correct |
| 14 |
Correct |
53 ms |
13000 KB |
Output is correct |
| 15 |
Correct |
44 ms |
16100 KB |
Output is correct |
| 16 |
Correct |
56 ms |
17224 KB |
Output is correct |
| 17 |
Correct |
43 ms |
11464 KB |
Output is correct |
| 18 |
Correct |
44 ms |
14788 KB |
Output is correct |
| 19 |
Correct |
363 ms |
84900 KB |
Output is correct |
| 20 |
Correct |
351 ms |
63596 KB |
Output is correct |
| 21 |
Correct |
338 ms |
83732 KB |
Output is correct |
| 22 |
Correct |
355 ms |
91704 KB |
Output is correct |
| 23 |
Correct |
150 ms |
55824 KB |
Output is correct |
| 24 |
Correct |
383 ms |
62992 KB |
Output is correct |
| 25 |
Correct |
355 ms |
78520 KB |
Output is correct |
