#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#define X first
#define Y second
#define PB push_back
using namespace std;
typedef pair < int, int > pii;
typedef vector < int > vi;
const int N = 5e5 + 5;
int bio[N], n, m, nod[N],ind[N], rek[N], cur;
vector < pii > v[N];
int tura[N], st[N], tr, ss, v1[N], v2[N], deg[N];
inline bool is( const char &c ) { return c >= '0' && c <= '9'; }
inline int read_int( ) {
int num;
char c;
while( !is( c = getchar_unlocked( ) ) );
num = c - '0';
while( is( c = getchar_unlocked( ) ) ) num = num * 10 + c - '0';
return num;
}
inline void euler(){
rek[cur++] = 1;
for(;cur;){
int x = rek[cur - 1];
for(;ind[x] < v[x].size() && bio[v[x][ind[x]].Y];++ind[x]);
if(ind[x] == v[x].size()) --cur, tura[tr++] = x;
for(;ind[x] < v[x].size();++ind[x]){
if(bio[v[x][ind[x]].Y]) continue;
bio[v[x][ind[x]].Y] = 1;
int nxt = v[x][ind[x]].X;
rek[cur++] = nxt;
break;
}
}
}
inline void rastavi(){
memset(bio, 0, sizeof(bio));
for(int i = 0;i < tr;++i){
if(bio[tura[i]]){
while(st[ss - 1] != tura[i]){
printf("%d ", st[ss - 1]);
bio[st[ss - 1]]--;
--ss;
}
--ss;
--bio[tura[i]];
printf("%d\n", tura[i]);
}
st[ss++] = tura[i];
++bio[tura[i]];
}
}
int main(){
n = read_int(); m = read_int();
for(int i = 0;i < m;++i){
v1[i] = read_int();
v2[i] = read_int();
deg[v1[i]]++, deg[v2[i]]++;
}
for(int i = 1;i <= n;i++){
v[i].resize(deg[i] + 1);
deg[i] = 0;
}
for(int i = 0;i < m;i++){
v[v1[i]][deg[v1[i]]++].X = v2[i];
v[v1[i]][deg[v1[i]] - 1].Y = i;
v[v2[i]][deg[v2[i]]++].X = v1[i];
v[v2[i]][deg[v2[i]] - 1].Y = i;
}
euler();
rastavi();
return 0;
}
Compilation message
postmen.cpp: In function 'void euler()':
postmen.cpp:37:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(;ind[x] < v[x].size() && bio[v[x][ind[x]].Y];++ind[x]);
~~~~~~~^~~~~~~~~~~~~
postmen.cpp:38:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(ind[x] == v[x].size()) --cur, tura[tr++] = x;
~~~~~~~^~~~~~~~~~~~~~
postmen.cpp:39:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(;ind[x] < v[x].size();++ind[x]){
~~~~~~~^~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
14080 KB |
Output is correct |
2 |
Correct |
13 ms |
14080 KB |
Output is correct |
3 |
Correct |
15 ms |
14080 KB |
Output is correct |
4 |
Correct |
17 ms |
14208 KB |
Output is correct |
5 |
Correct |
16 ms |
14080 KB |
Output is correct |
6 |
Correct |
14 ms |
14208 KB |
Output is correct |
7 |
Correct |
16 ms |
14600 KB |
Output is correct |
8 |
Correct |
14 ms |
14208 KB |
Output is correct |
9 |
Correct |
35 ms |
17528 KB |
Output is correct |
10 |
Incorrect |
15 ms |
14208 KB |
Edge does not exist or used 757, 1097 |
11 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
14080 KB |
Output is correct |
2 |
Correct |
16 ms |
14080 KB |
Output is correct |
3 |
Correct |
15 ms |
14080 KB |
Output is correct |
4 |
Correct |
13 ms |
14208 KB |
Output is correct |
5 |
Correct |
13 ms |
14080 KB |
Output is correct |
6 |
Correct |
13 ms |
14208 KB |
Output is correct |
7 |
Correct |
17 ms |
14568 KB |
Output is correct |
8 |
Correct |
13 ms |
14208 KB |
Output is correct |
9 |
Correct |
39 ms |
17588 KB |
Output is correct |
10 |
Incorrect |
14 ms |
14208 KB |
Edge does not exist or used 757, 1097 |
11 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
14080 KB |
Output is correct |
2 |
Correct |
14 ms |
14020 KB |
Output is correct |
3 |
Correct |
14 ms |
14080 KB |
Output is correct |
4 |
Correct |
13 ms |
14208 KB |
Output is correct |
5 |
Correct |
13 ms |
14080 KB |
Output is correct |
6 |
Correct |
15 ms |
14208 KB |
Output is correct |
7 |
Correct |
37 ms |
14592 KB |
Output is correct |
8 |
Correct |
16 ms |
14208 KB |
Output is correct |
9 |
Correct |
35 ms |
17632 KB |
Output is correct |
10 |
Incorrect |
13 ms |
14208 KB |
Edge does not exist or used 757, 1097 |
11 |
Halted |
0 ms |
0 KB |
- |