結果
問題 | No.1254 補強への架け橋 |
ユーザー |
|
提出日時 | 2020-10-09 21:45:44 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 128 ms / 2,000 ms |
コード長 | 1,336 bytes |
コンパイル時間 | 909 ms |
コンパイル使用メモリ | 81,344 KB |
実行使用メモリ | 20,224 KB |
最終ジャッジ日時 | 2024-07-20 10:20:21 |
合計ジャッジ時間 | 12,181 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 123 |
コンパイルメッセージ
main.cpp:55:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type] 55 | main() | ^~~~
ソースコード
#include<iostream> using namespace std; #include<vector> #include<algorithm> struct bridge{ vector<int>ord,low; vector<bool>art; vector<pair<int,int> >bridges; vector<vector<int> >G; bridge(int n_=0):ord(n_,-1),low(n_),art(n_,false),G(n_){} void add_edge(int u,int v) { G[u].push_back(v); G[v].push_back(u); } bool operator[](int a)const{return art[a];} bool is_bridge(int a,int b)const { if(ord[a]>ord[b])swap(a,b); return ord[a]<low[b]; } void dfs(int u,int p,int&k) { low[u]=ord[u]=k++; for(int&v:G[u]) { if(ord[v]==-1) { dfs(v,u,k); low[u]=min(low[u],low[v]); art[u]=art[u]|ord[u]<=low[v]; if(ord[u]<low[v])bridges.push_back(u<v?make_pair(u,v):make_pair(v,u)); } else if(v!=p) { low[u]=min(low[u],ord[v]); } } } void build() { int k=1,cnt=0; low[0]=ord[0]=0; for(int&v:G[0])if(ord[v]==-1) { dfs(v,0,k); if(ord[0]<low[v])bridges.push_back(make_pair(0,v)); cnt++; } if(cnt>=2)art[0]=true; } }; int N; int u[1<<17],v[1<<17]; main() { cin>>N; bridge P(N); for(int i=0;i<N;i++) { cin>>u[i]>>v[i]; u[i]--,v[i]--; P.add_edge(u[i],v[i]); } P.build(); vector<int>ans; for(int i=0;i<N;i++)if(!P.is_bridge(u[i],v[i]))ans.push_back(i+1); cout<<ans.size()<<endl; for(int i=0;i<ans.size();i++)cout<<ans[i]<<(i+1==ans.size()?"\n":" "); }