Codeforces ECR #072 : D. Coloring Edges

意外にシンプルな問題ながらAC数が少ない。
https://codeforces.com/contest/1217/problem/D

問題

有向グラフが与えられる。
辺を彩色し、同色の閉路ができないようにせよ。

解法

基本的に同色で彩色して、閉路ができそうな最後の辺だけ2色目を使えばよい。

int N,M;
vector<int> E[5050];
int S[5050],T[5050],C[5050];
int vis[5050];
int K;

void dfs(int cur) {
	vis[cur]=2;
	FORR(e,E[cur]) if(C[e]==0) {
		if(vis[T[e]]==2) {
			C[e]=1;
			K=1;
		}
		else if(vis[T[e]]==0) {
			dfs(T[e]);
		}
	}
	vis[cur]=1;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>S[i]>>T[i];
		S[i]--;
		T[i]--;
		E[S[i]].push_back(i);
	}
	
	FOR(i,N) {
		ZERO(vis);
		dfs(i);
	}
	
	cout<<K+1<<endl;
	FOR(i,M) cout<<C[i]+1<<" ";
}

まとめ

ようやく9月分に入ったか…。