この難易度でなんで2:30だったんだろ。
https://yukicoder.me/problems/no/1254
問題
N頂点N辺の連結グラフが与えられる。
ここから1辺取り除いてもグラフが連結のままであるような辺を列挙せよ。
解法
橋でないものを求めればよいので、橋検出を行ってもよい。
別解法としては、次数1の頂点とそれに付随する辺を取り除く、を繰り返すと最後に1つ閉路が残るのでそこが問題の指定する辺の集合になる。
以下の解法は後者。
int N; set<pair<int,int>> E[303030]; int need[303030]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N) { cin>>x>>y; E[x-1].insert({y-1,i}); E[y-1].insert({x-1,i}); } queue<int> Q; FOR(i,N) if(E[i].size()==1) Q.push(i); while(Q.size()) { x=Q.front(); Q.pop(); y=E[x].begin()->first; i=E[x].begin()->second; need[i]=1; E[x].clear(); E[y].erase({x,i}); if(E[y].size()==1) Q.push(y); } cout<<count(need,need+N,0)<<endl; FOR(i,N) if(need[i]==0) cout<<(i+1)<<" "; cout<<endl; }
まとめ
まぁ参加が遅くて全完間に合わなかったんですけどね…。