結果
問題 | No.1254 補強への架け橋 |
ユーザー |
![]() |
提出日時 | 2020-10-09 23:15:23 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 294 ms / 2,000 ms |
コード長 | 1,409 bytes |
コンパイル時間 | 1,874 ms |
コンパイル使用メモリ | 182,672 KB |
実行使用メモリ | 38,272 KB |
最終ジャッジ日時 | 2024-07-20 14:09:35 |
合計ジャッジ時間 | 14,081 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 123 |
ソースコード
#include <bits/stdc++.h> #define rep(i,n) for (int i = 0; i < (n); ++i) #define chmax(a, b) a = max(a, b) #define chmin(a, b) a = min(a, b) #define all(x) (x).begin(), (x).end() using namespace std; using ll = long long; using P = pair<int,int>; using VI = vector<int>; using VVI = vector<VI>; VVI to; int n; map<P, int> bmap; VI parent, depth; vector<int> ans; bool dfs(int u, int d=0, int p=-1) { parent[u] = p; depth[u] = d; for(int v: to[u]) { if (v == p) continue; if (depth[v] == -1) { if (dfs(v, d+1, u)) return true;; } else { ans.push_back(bmap[{u, v}]); while(u != v) { if (depth[u] >= depth[v]) { ans.push_back(bmap[{u, parent[u]}]); u = parent[u]; } else { ans.push_back(bmap[{v, parent[v]}]); v = parent[v]; } } return true; } } return false; } int main() { cin >> n; to = VVI(n); depth = VI(n, -1); parent = VI(n, -1); rep(i, n) { int a, b; cin >> a >> b; a--; b--; bmap[{a, b}] = bmap[{b, a}] = i + 1; to[a].push_back(b); to[b].push_back(a); } dfs(0); sort(all(ans)); cout << ans.size() << endl; rep(i, ans.size()) cout << ans[i] << " \n"[i + 1 == ans.size()]; }