#include <bits/stdc++.h>
using namespace std;
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int N, M;
cin >> N >> M;
vector<vector<pair<int, int>>> G(N);
for (int i = 0; i < M; i++) {
int u, v;
cin >> u >> v;
u--, v--;
G[u].push_back({v, i});
G[v].push_back({u, i});
}
vector<int> ptr(N);
vector<bool> used(M);
vector<int> path;
stack<int> s;
s.push(0);
while (!s.empty()) {
int u = s.top();
while (ptr[u] < (int)G[u].size() && used[G[u][ptr[u]].second]) {
ptr[u]++;
}
if (ptr[u] == (int)G[u].size()) {
path.push_back(u);
s.pop();
} else {
used[G[u][ptr[u]].second] = true;
s.push(G[u][ptr[u]++].first);
}
}
vector<bool> occ(N, false);
vector<vector<int>> cycles;
vector<int> b;
for (int v : path) {
b.push_back(v);
if (occ[v]) {
cycles.push_back({});
cycles.back().push_back(v);
b.pop_back();
while (b.back() != v) {
cycles.back().push_back(b.back());
occ[b.back()] = false;
b.pop_back();
}
} else {
occ[v] = true;
}
}
for (auto cycle : cycles) {
int k = (int)cycle.size();
for (int i = 0; i < k; i++) {
cout << 1 + cycle[i] << " \n"[i + 1 == k];
}
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
2 ms |
468 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Correct |
4 ms |
992 KB |
Output is correct |
8 |
Correct |
1 ms |
468 KB |
Output is correct |
9 |
Correct |
24 ms |
3704 KB |
Output is correct |
10 |
Correct |
2 ms |
468 KB |
Output is correct |
11 |
Correct |
2 ms |
468 KB |
Output is correct |
12 |
Correct |
26 ms |
4064 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
2 ms |
468 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
2 ms |
468 KB |
Output is correct |
7 |
Correct |
4 ms |
980 KB |
Output is correct |
8 |
Correct |
1 ms |
468 KB |
Output is correct |
9 |
Correct |
21 ms |
3660 KB |
Output is correct |
10 |
Correct |
2 ms |
468 KB |
Output is correct |
11 |
Correct |
1 ms |
468 KB |
Output is correct |
12 |
Correct |
23 ms |
4036 KB |
Output is correct |
13 |
Correct |
32 ms |
9028 KB |
Output is correct |
14 |
Correct |
38 ms |
7620 KB |
Output is correct |
15 |
Correct |
35 ms |
7908 KB |
Output is correct |
16 |
Correct |
37 ms |
8992 KB |
Output is correct |
17 |
Correct |
42 ms |
7836 KB |
Output is correct |
18 |
Correct |
43 ms |
7828 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
2 ms |
468 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
2 ms |
468 KB |
Output is correct |
7 |
Correct |
4 ms |
980 KB |
Output is correct |
8 |
Correct |
1 ms |
468 KB |
Output is correct |
9 |
Correct |
28 ms |
3624 KB |
Output is correct |
10 |
Correct |
2 ms |
468 KB |
Output is correct |
11 |
Correct |
1 ms |
540 KB |
Output is correct |
12 |
Correct |
24 ms |
4048 KB |
Output is correct |
13 |
Correct |
33 ms |
8948 KB |
Output is correct |
14 |
Correct |
34 ms |
7580 KB |
Output is correct |
15 |
Correct |
46 ms |
7972 KB |
Output is correct |
16 |
Correct |
45 ms |
9028 KB |
Output is correct |
17 |
Correct |
49 ms |
7848 KB |
Output is correct |
18 |
Correct |
35 ms |
7752 KB |
Output is correct |
19 |
Correct |
295 ms |
44024 KB |
Output is correct |
20 |
Correct |
297 ms |
37508 KB |
Output is correct |
21 |
Correct |
327 ms |
36256 KB |
Output is correct |
22 |
Correct |
307 ms |
44012 KB |
Output is correct |
23 |
Correct |
115 ms |
15672 KB |
Output is correct |
24 |
Correct |
332 ms |
37528 KB |
Output is correct |
25 |
Correct |
292 ms |
44464 KB |
Output is correct |