#include <bits/stdc++.h>
using namespace std;
int ctrl[500005];
int nxt[1000005], prv[1000005], id[1000005];
int head[500005], en[500005];
bool visited[500005];
int n,m;
int euler[1000005], eulersize;
int q[1000005], qsize;
int read_int(){
char c;
bool check = 0;
int res = 0;
while(1){
c = getchar();
if (c == '-') {check = 1; continue;}
if (c == ' ' || c == '\n') break;
res = res*10 + c - '0';
}
if (check) return -res;
return res;
}
void dfs(){
q[qsize++] = 1;
while(qsize){
int u = q[qsize-1];
bool mjk = 0;
for(;ctrl[u];ctrl[u] = nxt[ctrl[u]]){
int v = (u ^ head[id[ctrl[u]]] ^ en[id[ctrl[u]]]);
if (visited[id[ctrl[u]]]) continue;
mjk = 1;
visited[id[ctrl[u]]] = 1;
q[qsize++] = v;
break;
}
if(mjk) continue;
euler[eulersize++] = u;
--qsize;
}
}
int st[1000005], stsize;
bool used[1000005];
int main(){
n = read_int();
m = read_int();
int cnt = 0;
for(int i=1;i<=m;++i){
int x = read_int(),y = read_int();
if (!ctrl[x]) ctrl[x] = ++cnt;
else nxt[prv[x]] = ++cnt;
id[cnt] = i;
prv[x] = cnt;
if (!ctrl[y]) ctrl[y] = ++cnt;
else nxt[prv[y]] = ++cnt;
id[cnt] = i;
prv[y] = cnt;
head[i] = x;
en[i] = y;
}
dfs();
for(int i=0;i<eulersize;++i){
if (used[euler[i]]){
while(st[stsize-1] != euler[i]){
printf("%d ",st[stsize-1]);
used[st[stsize-1]] = 0;
--stsize;
};
printf("%d\n",euler[i]);
}
else{
st[stsize++] = euler[i];
used[euler[i]] = 1;
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
6 ms |
512 KB |
Output is correct |
5 |
Correct |
5 ms |
512 KB |
Output is correct |
6 |
Correct |
6 ms |
640 KB |
Output is correct |
7 |
Correct |
8 ms |
1024 KB |
Output is correct |
8 |
Correct |
5 ms |
512 KB |
Output is correct |
9 |
Correct |
31 ms |
4060 KB |
Output is correct |
10 |
Correct |
5 ms |
512 KB |
Output is correct |
11 |
Correct |
5 ms |
512 KB |
Output is correct |
12 |
Correct |
34 ms |
4096 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
512 KB |
Output is correct |
5 |
Correct |
6 ms |
384 KB |
Output is correct |
6 |
Correct |
6 ms |
512 KB |
Output is correct |
7 |
Correct |
9 ms |
1024 KB |
Output is correct |
8 |
Correct |
5 ms |
512 KB |
Output is correct |
9 |
Correct |
29 ms |
3960 KB |
Output is correct |
10 |
Correct |
7 ms |
512 KB |
Output is correct |
11 |
Correct |
5 ms |
512 KB |
Output is correct |
12 |
Correct |
37 ms |
4088 KB |
Output is correct |
13 |
Correct |
43 ms |
5496 KB |
Output is correct |
14 |
Correct |
43 ms |
4856 KB |
Output is correct |
15 |
Correct |
37 ms |
4728 KB |
Output is correct |
16 |
Correct |
43 ms |
5496 KB |
Output is correct |
17 |
Correct |
46 ms |
4448 KB |
Output is correct |
18 |
Correct |
43 ms |
4924 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
432 KB |
Output is correct |
4 |
Correct |
6 ms |
544 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
640 KB |
Output is correct |
7 |
Correct |
11 ms |
896 KB |
Output is correct |
8 |
Correct |
5 ms |
512 KB |
Output is correct |
9 |
Correct |
33 ms |
3960 KB |
Output is correct |
10 |
Correct |
5 ms |
512 KB |
Output is correct |
11 |
Correct |
5 ms |
512 KB |
Output is correct |
12 |
Correct |
34 ms |
4088 KB |
Output is correct |
13 |
Correct |
42 ms |
5496 KB |
Output is correct |
14 |
Correct |
47 ms |
4856 KB |
Output is correct |
15 |
Correct |
41 ms |
4680 KB |
Output is correct |
16 |
Correct |
48 ms |
5444 KB |
Output is correct |
17 |
Correct |
49 ms |
4484 KB |
Output is correct |
18 |
Correct |
52 ms |
4980 KB |
Output is correct |
19 |
Correct |
374 ms |
26308 KB |
Output is correct |
20 |
Correct |
340 ms |
23128 KB |
Output is correct |
21 |
Correct |
316 ms |
22008 KB |
Output is correct |
22 |
Correct |
367 ms |
26244 KB |
Output is correct |
23 |
Correct |
136 ms |
18424 KB |
Output is correct |
24 |
Correct |
396 ms |
20960 KB |
Output is correct |
25 |
Correct |
366 ms |
23052 KB |
Output is correct |