結果
問題 |
No.1254 補強への架け橋
|
ユーザー |
👑 ![]() |
提出日時 | 2020-10-09 21:48:10 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 161 ms / 2,000 ms |
コード長 | 1,227 bytes |
コンパイル時間 | 1,863 ms |
コンパイル使用メモリ | 172,768 KB |
実行使用メモリ | 26,728 KB |
最終ジャッジ日時 | 2024-07-20 10:31:37 |
合計ジャッジ時間 | 14,425 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 123 |
ソースコード
#include<bits/stdc++.h> using namespace std; using LL = long long; using ULL = unsigned long long; #define rep(i,n) for(int i=0; i<(n); i++) const int xN = 100000; int N, M; vector<int> E[xN], rE[xN]; int I[xN], rI[xN]; int P[xN], H[xN]; LL ans = 0; int DFS1(int p, int i = 0) { for (int e : E[p]) { if (P[p] == e) continue; rE[e].push_back(p); if (P[e] != -1) continue; P[e] = p; i = DFS1(e, i); } I[p] = i; rI[i] = p; ++i; return i; } void DFS2(int p, int s) { if (rI[I[p]] != p) return; H[p] = s; for (int e : rE[p]) { if (I[e] > I[s]) continue; if (H[e] != -1) continue; DFS2(e, s); } } void strongDc() { rep(i, N) P[i] = I[i] = H[i] = -1; rep(i, N) { if (P[i] != -1) continue; P[i] = i; int Z = DFS1(i); for (int i = Z - 1; i != -1; i--) if (H[rI[i]] == -1) DFS2(rI[i], rI[i]); } } vector<pair<int, int>> J; int main() { cin >> N; rep(i, N) { int u, v; cin >> u >> v; u--; v--; J.push_back({ u,v }); E[u].push_back(v); E[v].push_back(u); } strongDc(); vector<int> ans; rep(i, N) { if (H[J[i].first] == H[J[i].second]) ans.push_back(i); } cout << ans.size() << endl; rep(i, ans.size()) { if (i) cout << " "; cout << (ans[i] + 1); } cout << endl; return 0; }