#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <chrono>
#include <random>
#include <functional>
using namespace std;
const int N = 5e5 + 7;
struct Edge {
int u, v;
int alive;
Edge() {}
Edge(int u_, int v_) {
u = u_;
v = v_;
alive = 1;
}
};
int in[N];
int et[N];
Edge ed[N];
int g[2 * N];
int pnts[N];
int deg[N];
int start[N];
int P = 0;
void dfs(int cur) {
for (; pnts[cur] < deg[cur]; pnts[cur]++) {
int ind = g[pnts[cur] + start[cur]];
if (ed[ind].alive) {
ed[ind].alive = 0;
int v = ed[ind].u;
if (v == cur) {
v = ed[ind].v;
}
dfs(v);
}
}
et[P] = cur;
P++;
}
int st[N];
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
cin >> ed[i].u >> ed[i].v;
ed[i].alive = 1;
ed[i].u--;
ed[i].v--;
deg[ed[i].u]++;
deg[ed[i].v]++;
}
for (int i = 1; i < n; i++) {
start[i] = start[i - 1] + deg[i - 1];
}
for (int i = 0; i < m; i++) {
int u, v;
u = ed[i].u;
v = ed[i].v;
g[start[u] + pnts[u]] = i;
g[start[v] + pnts[v]] = i;
pnts[u]++;
pnts[v]++;
}
for (int i = 0; i < n; i++) {
pnts[i] = 0;
}
dfs(0);
int P2 = 0;
for (int i = 0; i < P; i++) {
int t = et[i];
if (in[t] > 0) {
while (true) {
in[st[P2 - 1]]--;
cout << st[P2 - 1] + 1 << ' ';
P2--;
if (st[P2] == t) break;
}
cout << '\n';
}
in[t]++;
st[P2] = t;
P2++;
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
640 KB |
Output is correct |
5 |
Correct |
1 ms |
512 KB |
Output is correct |
6 |
Correct |
2 ms |
640 KB |
Output is correct |
7 |
Correct |
5 ms |
1280 KB |
Output is correct |
8 |
Correct |
1 ms |
512 KB |
Output is correct |
9 |
Correct |
34 ms |
6264 KB |
Output is correct |
10 |
Correct |
1 ms |
512 KB |
Output is correct |
11 |
Correct |
2 ms |
512 KB |
Output is correct |
12 |
Correct |
35 ms |
6392 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
640 KB |
Output is correct |
5 |
Correct |
1 ms |
512 KB |
Output is correct |
6 |
Correct |
2 ms |
640 KB |
Output is correct |
7 |
Correct |
6 ms |
1280 KB |
Output is correct |
8 |
Correct |
1 ms |
512 KB |
Output is correct |
9 |
Correct |
32 ms |
6264 KB |
Output is correct |
10 |
Correct |
1 ms |
512 KB |
Output is correct |
11 |
Correct |
1 ms |
512 KB |
Output is correct |
12 |
Correct |
38 ms |
6396 KB |
Output is correct |
13 |
Correct |
42 ms |
8440 KB |
Output is correct |
14 |
Correct |
40 ms |
6272 KB |
Output is correct |
15 |
Correct |
41 ms |
7416 KB |
Output is correct |
16 |
Correct |
41 ms |
8440 KB |
Output is correct |
17 |
Correct |
42 ms |
4728 KB |
Output is correct |
18 |
Correct |
40 ms |
6904 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
640 KB |
Output is correct |
5 |
Correct |
1 ms |
512 KB |
Output is correct |
6 |
Correct |
3 ms |
640 KB |
Output is correct |
7 |
Correct |
6 ms |
1280 KB |
Output is correct |
8 |
Correct |
1 ms |
512 KB |
Output is correct |
9 |
Correct |
42 ms |
6264 KB |
Output is correct |
10 |
Correct |
2 ms |
512 KB |
Output is correct |
11 |
Correct |
1 ms |
512 KB |
Output is correct |
12 |
Correct |
36 ms |
6392 KB |
Output is correct |
13 |
Correct |
42 ms |
8440 KB |
Output is correct |
14 |
Correct |
40 ms |
6264 KB |
Output is correct |
15 |
Correct |
42 ms |
7416 KB |
Output is correct |
16 |
Correct |
40 ms |
8448 KB |
Output is correct |
17 |
Correct |
54 ms |
4728 KB |
Output is correct |
18 |
Correct |
48 ms |
6908 KB |
Output is correct |
19 |
Correct |
300 ms |
40956 KB |
Output is correct |
20 |
Correct |
237 ms |
30216 KB |
Output is correct |
21 |
Correct |
346 ms |
35776 KB |
Output is correct |
22 |
Correct |
241 ms |
40952 KB |
Output is correct |
23 |
Correct |
162 ms |
29688 KB |
Output is correct |
24 |
Correct |
287 ms |
22136 KB |
Output is correct |
25 |
Correct |
240 ms |
33656 KB |
Output is correct |