色々グダった回。
http://codeforces.com/contest/915/problem/D
問題
有向グラフが与えられる。
辺を1つ取り除き、閉路をなくすことができるか。
解法
まず初期グラフで閉路を求めよう。
なくすべき辺はこの閉路上のどこかにあるので、各辺を総当たりしよう。
閉路上の辺にフォーカスすることで、探索対象の辺を絞れる。
int N,M; vector<int> E[505]; int vis[505],vis2[505]; vector<int> V; vector<int> cand; int L,R; void dfs(int cur) { if(vis2[cur]) return; vis[cur]++; if(vis[cur]>=2) { int i; for(i=V.size()-1;i>=0;i--) { cand.push_back(V[i]); if(V[i]==cur) break; } reverse(ALL(cand)); cand.push_back(cur); return; } V.push_back(cur); FORR(r,E[cur]) { if(cand.empty()) dfs(r); } V.pop_back(); vis2[cur]++; } int acyclic(int L,int R) { int in[505]={}; int i; FOR(i,N) FORR(e,E[i]) if(L!=i || R!=e) in[e]++; queue<int> Q; FOR(i,N) if(in[i]==0) Q.push(i); int left=N; while(Q.size()) { int cur=Q.front(); left--; Q.pop(); FORR(e,E[cur]) { if(L==cur && R==e) continue; in[e]--; if(in[e]==0) Q.push(e); } } return left==0; } void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M; FOR(i,M) { cin>>x>>y; x--,y--; E[x].push_back(y); } FOR(i,N) if(vis2[i]==0 && cand.empty()) { ZERO(vis); V.clear(); dfs(i); } if(cand.empty()) return _P("YES\n"); FOR(i,cand.size()-1) if(acyclic(cand[i],cand[i+1])) return _P("YES\n"); _P("NO\n"); }
まとめ
なんでこれ落としたんだ…。