#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("03")
#define int long long
#define ll long long
#define pii pair<int, int>
#define F first
#define S second
#define PB push_back
#define ALL(x) x.begin(), x.end()
#define FOR(i, n) for (int i = 0; i < n; i++)
#define NYOOM ios::sync_with_stdio(0); cin.tie(0);
#define endl '\n'
const int INF = 1e9 + 7;
const ll LLINF = 1ll<<60;
const int maxn = 5e5 + 10;
int n, m, to_parent[maxn], parent[maxn], rem[maxn] = {0}, idx[maxn] = {0};
pii edge[maxn];
bool seen[maxn] = {0}, deleted[maxn] = {0};
vector<pii> adj[maxn];
void dfs(int start){
stack<int> s;
s.push(start);
while (!s.empty()){
int v = s.top(); seen[v] = true;
while (idx[v] < adj[v].size()){
int u = adj[v][idx[v]].F, i = adj[v][idx[v]].S; idx[v]++;
if (deleted[i] || u == parent[v]){
continue;
}
if (!seen[u]){
parent[u] = v; to_parent[u] = i;
s.push(u); break;
}
rem[v]--; rem[u]--; deleted[i] = true;
while (s.top() != u){
cout << s.top() << ' ';
rem[s.top()]--; rem[parent[s.top()]]--;
deleted[to_parent[s.top()]] = true;
seen[s.top()] = false; s.pop();
}
cout << u << endl;
if (rem[u] == 0) s.pop();
break;
}
}
}
signed main(){
NYOOM;
cin >> n >> m;
FOR(i, m){
int u, v; cin >> u >> v; edge[i] = {u, v};
rem[u]++; rem[v]++;
adj[u].PB({v, i}); adj[v].PB({u, i});
}
for (int v = 1; v <= n; v++){
while (rem[v] > 0) dfs(v);
}
}
Compilation message
postmen.cpp: In function 'void dfs(long long int)':
postmen.cpp:30:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | while (idx[v] < adj[v].size()){
| ~~~~~~~^~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
12116 KB |
Output is correct |
2 |
Correct |
8 ms |
12060 KB |
Output is correct |
3 |
Correct |
7 ms |
12076 KB |
Output is correct |
4 |
Correct |
8 ms |
12372 KB |
Output is correct |
5 |
Correct |
8 ms |
12104 KB |
Output is correct |
6 |
Correct |
8 ms |
12372 KB |
Output is correct |
7 |
Correct |
12 ms |
13348 KB |
Output is correct |
8 |
Correct |
9 ms |
12340 KB |
Output is correct |
9 |
Correct |
33 ms |
18700 KB |
Output is correct |
10 |
Correct |
9 ms |
12372 KB |
Output is correct |
11 |
Correct |
9 ms |
12344 KB |
Output is correct |
12 |
Correct |
40 ms |
19248 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
12116 KB |
Output is correct |
2 |
Correct |
8 ms |
12116 KB |
Output is correct |
3 |
Correct |
7 ms |
12116 KB |
Output is correct |
4 |
Correct |
10 ms |
12372 KB |
Output is correct |
5 |
Correct |
8 ms |
12116 KB |
Output is correct |
6 |
Correct |
10 ms |
12372 KB |
Output is correct |
7 |
Correct |
12 ms |
13396 KB |
Output is correct |
8 |
Correct |
8 ms |
12288 KB |
Output is correct |
9 |
Correct |
34 ms |
18724 KB |
Output is correct |
10 |
Correct |
9 ms |
12372 KB |
Output is correct |
11 |
Correct |
10 ms |
12468 KB |
Output is correct |
12 |
Correct |
43 ms |
19276 KB |
Output is correct |
13 |
Correct |
72 ms |
24140 KB |
Output is correct |
14 |
Correct |
63 ms |
22040 KB |
Output is correct |
15 |
Correct |
67 ms |
21560 KB |
Output is correct |
16 |
Correct |
71 ms |
24124 KB |
Output is correct |
17 |
Correct |
92 ms |
21868 KB |
Output is correct |
18 |
Correct |
77 ms |
22200 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
12076 KB |
Output is correct |
2 |
Correct |
7 ms |
12072 KB |
Output is correct |
3 |
Correct |
7 ms |
12116 KB |
Output is correct |
4 |
Correct |
8 ms |
12372 KB |
Output is correct |
5 |
Correct |
8 ms |
12116 KB |
Output is correct |
6 |
Correct |
8 ms |
12372 KB |
Output is correct |
7 |
Correct |
11 ms |
13364 KB |
Output is correct |
8 |
Correct |
8 ms |
12372 KB |
Output is correct |
9 |
Correct |
35 ms |
18656 KB |
Output is correct |
10 |
Correct |
8 ms |
12372 KB |
Output is correct |
11 |
Correct |
8 ms |
12316 KB |
Output is correct |
12 |
Correct |
40 ms |
19168 KB |
Output is correct |
13 |
Correct |
69 ms |
24168 KB |
Output is correct |
14 |
Correct |
67 ms |
22004 KB |
Output is correct |
15 |
Correct |
57 ms |
21364 KB |
Output is correct |
16 |
Correct |
60 ms |
24028 KB |
Output is correct |
17 |
Correct |
90 ms |
21792 KB |
Output is correct |
18 |
Correct |
70 ms |
22068 KB |
Output is correct |
19 |
Correct |
424 ms |
70748 KB |
Output is correct |
20 |
Correct |
425 ms |
59928 KB |
Output is correct |
21 |
Correct |
383 ms |
56996 KB |
Output is correct |
22 |
Correct |
433 ms |
70492 KB |
Output is correct |
23 |
Correct |
170 ms |
40452 KB |
Output is correct |
24 |
Correct |
484 ms |
58744 KB |
Output is correct |
25 |
Correct |
442 ms |
66616 KB |
Output is correct |