kmjp's blog

競技プログラミング参加記です

Codeforces ECR #036: D. Almost Acyclic Graph

色々グダった回。
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");
}

まとめ

なんでこれ落としたんだ…。