#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<string.h>
using namespace std;
int n, m;
int beg[1000100], des[1000100], nxt[1000100], pre[1000100];
vector<int> euler;
queue<int> chk[500100];
void erase_edge(int ptr, int v) {
if (beg[v]==ptr) beg[v]=nxt[ptr];
if (pre[ptr]!=-1) nxt[pre[ptr]] = nxt[ptr];
if (nxt[ptr]!=-1) pre[nxt[ptr]] = pre[ptr];
des[ptr] = -1;
}
int find(int u) {
if (u==-1||des[u]!=-1) return u;
return nxt[u] = find(nxt[u]);
}
void dfs(int here) {
int i;
for (i=beg[here];i!=-1;i=find(i)) {
int there = des[i];
erase_edge(i,here);
erase_edge(i^1,there);
dfs(there);
}
chk[here].push(euler.size());
euler.push_back(here);
}
queue<pair<int,int> > q;
void ans() {
int i;
q.push(pair<int,int>(0,euler.size()-1));
while(!q.empty()) {
int s = q.front().first, e = q.front().second;
q.pop();
for (i=s;i<e;i++) {
if (i!=s) chk[euler[i]].pop();
if (i!=s&&!chk[euler[i]].empty()&&chk[euler[i]].front()<e) {
q.push(pair<int,int>(i,chk[euler[i]].front()));
i=chk[euler[i]].front();
}
printf("%d ",euler[i]+1);
}
printf("\n");
}
}
void process() {
dfs(0);
chk[euler[0]].pop();
ans();
}
int ptr = 0;
void real_add_edge(int u, int v) {
nxt[ptr] = beg[u];
pre[beg[u]] = ptr;
des[ptr] = v;
pre[ptr] = -1;
beg[u] = ptr++;
}
void add_edge(int u, int v) {real_add_edge(u,v);real_add_edge(v,u);}
void input() {
int i;
scanf("%d %d",&n,&m);
memset(beg,-1,sizeof(beg));
for (i=0;i<m;i++) {
int a, b;
scanf("%d %d",&a,&b);
add_edge(--a,--b);
}
}
int main() {
input();
process();
return 0;
}
Compilation message
postmen.cpp: In function 'void input()':
postmen.cpp:68:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&n,&m);
~~~~~^~~~~~~~~~~~~~~
postmen.cpp:72:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&a,&b);
~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
143 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
138 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
139 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
