#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
const int MOD = 1e9+7;
#define f first
#define s second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
void FASTIO() {ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); }
const int mxn = 5e5+5;
int n, m;
bool available[mxn];
vector<pii> adj[mxn];
bool in_stack[mxn];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for(int i = 0; i < m; i++) {
int a, b; cin >> a >> b;
available[i] = true;
adj[a].pb({b, i});
adj[b].pb({a, i});
}
vector<vi> ans;
stack<int> st;
for(int i = 1; i <= n; i++) {
while(!adj[i].empty() && !available[adj[i].back().s]) adj[i].pop_back();
if(adj[i].empty()) continue;
st.push(i);
in_stack[i] = true;
while(!st.empty()) {
int a = st.top();
while(!adj[a].empty() && !available[adj[a].back().s]) adj[a].pop_back();
int b = adj[a].back().f;
available[adj[a].back().s] = false;
adj[a].pop_back();
if(in_stack[b]) {
vi route;
while(st.top() != b) in_stack[st.top()] = false, route.pb(st.top()), st.pop();
while(!adj[b].empty() && !available[adj[b].back().s]) adj[b].pop_back();
if(adj[b].empty()) {
in_stack[b] = false;
st.pop();
}
route.pb(b);
ans.pb(route);
}
else {
in_stack[b] = true;
st.push(b);
}
}
}
for(auto v : ans) {
for(int a : v) {
cout << a << " ";
}
cout << "\n";
}
return 0;
}
/*
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
11988 KB |
Output is correct |
2 |
Correct |
6 ms |
11988 KB |
Output is correct |
3 |
Correct |
7 ms |
11988 KB |
Output is correct |
4 |
Correct |
9 ms |
12240 KB |
Output is correct |
5 |
Correct |
7 ms |
12016 KB |
Output is correct |
6 |
Correct |
8 ms |
12244 KB |
Output is correct |
7 |
Correct |
10 ms |
12756 KB |
Output is correct |
8 |
Correct |
7 ms |
12116 KB |
Output is correct |
9 |
Correct |
31 ms |
15116 KB |
Output is correct |
10 |
Correct |
7 ms |
12216 KB |
Output is correct |
11 |
Correct |
7 ms |
12212 KB |
Output is correct |
12 |
Correct |
35 ms |
15480 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
12076 KB |
Output is correct |
2 |
Correct |
7 ms |
12008 KB |
Output is correct |
3 |
Correct |
8 ms |
11988 KB |
Output is correct |
4 |
Correct |
8 ms |
12152 KB |
Output is correct |
5 |
Correct |
6 ms |
12116 KB |
Output is correct |
6 |
Correct |
7 ms |
12244 KB |
Output is correct |
7 |
Correct |
11 ms |
12756 KB |
Output is correct |
8 |
Correct |
7 ms |
12116 KB |
Output is correct |
9 |
Correct |
33 ms |
15116 KB |
Output is correct |
10 |
Correct |
7 ms |
12216 KB |
Output is correct |
11 |
Correct |
9 ms |
12212 KB |
Output is correct |
12 |
Correct |
38 ms |
15452 KB |
Output is correct |
13 |
Correct |
52 ms |
17372 KB |
Output is correct |
14 |
Correct |
54 ms |
17104 KB |
Output is correct |
15 |
Correct |
52 ms |
17600 KB |
Output is correct |
16 |
Correct |
52 ms |
17392 KB |
Output is correct |
17 |
Correct |
59 ms |
17764 KB |
Output is correct |
18 |
Correct |
54 ms |
17252 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
11988 KB |
Output is correct |
2 |
Correct |
7 ms |
11988 KB |
Output is correct |
3 |
Correct |
6 ms |
12020 KB |
Output is correct |
4 |
Correct |
7 ms |
12244 KB |
Output is correct |
5 |
Correct |
7 ms |
12116 KB |
Output is correct |
6 |
Correct |
8 ms |
12244 KB |
Output is correct |
7 |
Correct |
13 ms |
12724 KB |
Output is correct |
8 |
Correct |
7 ms |
12084 KB |
Output is correct |
9 |
Correct |
32 ms |
15100 KB |
Output is correct |
10 |
Correct |
8 ms |
12216 KB |
Output is correct |
11 |
Correct |
8 ms |
12144 KB |
Output is correct |
12 |
Correct |
37 ms |
15436 KB |
Output is correct |
13 |
Correct |
58 ms |
17340 KB |
Output is correct |
14 |
Correct |
55 ms |
17220 KB |
Output is correct |
15 |
Correct |
52 ms |
17572 KB |
Output is correct |
16 |
Correct |
47 ms |
17344 KB |
Output is correct |
17 |
Correct |
59 ms |
17736 KB |
Output is correct |
18 |
Correct |
53 ms |
17376 KB |
Output is correct |
19 |
Correct |
354 ms |
38336 KB |
Output is correct |
20 |
Correct |
374 ms |
37612 KB |
Output is correct |
21 |
Correct |
332 ms |
38212 KB |
Output is correct |
22 |
Correct |
360 ms |
38552 KB |
Output is correct |
23 |
Correct |
133 ms |
25444 KB |
Output is correct |
24 |
Correct |
442 ms |
39688 KB |
Output is correct |
25 |
Correct |
395 ms |
38524 KB |
Output is correct |