#include <bits/stdc++.h>
// #pragma GCC optimize ("Ofast,unroll-loops")
using namespace std;
typedef long long ll;
typedef pair<int, int> pp;
#define rep(i,l,r) for(int i = (l); i < (r); i++)
#define per(i,r,l) for(int i = (r); i >= (l); i--)
#define sz(x) (int)x.size()
#define ff first
#define ss second
#define all(x) begin(x), end(x)
#define pb push_back
const ll mod = 1e9+7, maxn = 5e5+5, inf = ll(1e9)+5;
vector<pp> adj[maxn];
bool vis[maxn], mrk[maxn];
vector<pp> edge;
void dfs(int r){
mrk[r] = true;
while(sz(adj[r])){
auto[id, u] = adj[r].back(); adj[r].pop_back();
if(vis[id]) continue;
vis[id] = true;
dfs(u);
edge.pb({r, u});
}
}
int main(){
cin.tie(0) -> sync_with_stdio(0);
//#ifndef ONLINE_JUDGE
// freopen("in.in", "r", stdin);
// freopen("out.out", "w", stdout);
//#endif
int n, m; cin >> n >> m;
rep(i,0,m){
int u, v; cin >> u >> v; u--, v--;
adj[u].pb({i, v}), adj[v].pb({i, u});
}
rep(i,0,n) if(!mrk[i]) dfs(i);
reverse(all(edge));
vector<int> stk{edge[0].ff};
fill(mrk, mrk + n, false); mrk[edge[0].ff] = true;
rep(i,0,m){
auto[u, v] = edge[i];
if(mrk[v]){
while(true){
int r = stk.back(); stk.pop_back();
mrk[r] = false;
cout << r+1 << ' ';
if(r == v) break;
} cout << '\n';
}
mrk[v] = true;
stk.pb(v);
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
12072 KB |
Output is correct |
2 |
Correct |
6 ms |
11988 KB |
Output is correct |
3 |
Correct |
7 ms |
11988 KB |
Output is correct |
4 |
Correct |
8 ms |
12336 KB |
Output is correct |
5 |
Correct |
6 ms |
12204 KB |
Output is correct |
6 |
Correct |
9 ms |
12596 KB |
Output is correct |
7 |
Correct |
10 ms |
13836 KB |
Output is correct |
8 |
Correct |
7 ms |
12244 KB |
Output is correct |
9 |
Correct |
36 ms |
22384 KB |
Output is correct |
10 |
Correct |
7 ms |
12344 KB |
Output is correct |
11 |
Correct |
10 ms |
12268 KB |
Output is correct |
12 |
Correct |
39 ms |
22880 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
11976 KB |
Output is correct |
2 |
Correct |
6 ms |
11988 KB |
Output is correct |
3 |
Correct |
6 ms |
12072 KB |
Output is correct |
4 |
Correct |
7 ms |
12372 KB |
Output is correct |
5 |
Correct |
8 ms |
12200 KB |
Output is correct |
6 |
Correct |
8 ms |
12628 KB |
Output is correct |
7 |
Correct |
11 ms |
13844 KB |
Output is correct |
8 |
Correct |
11 ms |
12212 KB |
Output is correct |
9 |
Correct |
49 ms |
22464 KB |
Output is correct |
10 |
Correct |
7 ms |
12244 KB |
Output is correct |
11 |
Correct |
8 ms |
12372 KB |
Output is correct |
12 |
Correct |
38 ms |
22840 KB |
Output is correct |
13 |
Correct |
61 ms |
25088 KB |
Output is correct |
14 |
Correct |
49 ms |
21208 KB |
Output is correct |
15 |
Correct |
47 ms |
23488 KB |
Output is correct |
16 |
Correct |
68 ms |
25008 KB |
Output is correct |
17 |
Correct |
55 ms |
18152 KB |
Output is correct |
18 |
Correct |
50 ms |
22524 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
11988 KB |
Output is correct |
2 |
Correct |
6 ms |
11988 KB |
Output is correct |
3 |
Correct |
7 ms |
12076 KB |
Output is correct |
4 |
Correct |
7 ms |
12340 KB |
Output is correct |
5 |
Correct |
6 ms |
12116 KB |
Output is correct |
6 |
Correct |
8 ms |
12628 KB |
Output is correct |
7 |
Correct |
11 ms |
13908 KB |
Output is correct |
8 |
Correct |
7 ms |
12212 KB |
Output is correct |
9 |
Correct |
35 ms |
22352 KB |
Output is correct |
10 |
Correct |
8 ms |
12336 KB |
Output is correct |
11 |
Correct |
7 ms |
12372 KB |
Output is correct |
12 |
Correct |
37 ms |
22852 KB |
Output is correct |
13 |
Correct |
54 ms |
25088 KB |
Output is correct |
14 |
Correct |
59 ms |
21184 KB |
Output is correct |
15 |
Correct |
48 ms |
23488 KB |
Output is correct |
16 |
Correct |
56 ms |
25024 KB |
Output is correct |
17 |
Correct |
49 ms |
18148 KB |
Output is correct |
18 |
Correct |
50 ms |
22532 KB |
Output is correct |
19 |
Correct |
383 ms |
77880 KB |
Output is correct |
20 |
Correct |
346 ms |
58800 KB |
Output is correct |
21 |
Correct |
333 ms |
68928 KB |
Output is correct |
22 |
Correct |
402 ms |
77956 KB |
Output is correct |
23 |
Correct |
158 ms |
62336 KB |
Output is correct |
24 |
Correct |
372 ms |
43056 KB |
Output is correct |
25 |
Correct |
345 ms |
65516 KB |
Output is correct |