kmjp's blog

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

TopCoderOpen 2018 Round3A Hard ColoringEdgesDiv1

適当に書いたら通ってしまった…。
http://community.topcoder.com/stat?c=problem_statement&pm=14909

問題

各頂点の次数が3であるような無向グラフが与えられる。
各辺を白黒2色で塗り分け、片方の色で構成される閉路ができないようにせよ。

解法

元グラフは森の可能性もあるので、以下個々の木について考える。
白色の辺が全域木を成すようにした場合、そもそも白色の辺は閉路を成さない。
ただ、全域木の作り方によっては黒色の辺が閉路を成すケースがある。

しかし、各頂点からDFSしてその経路の辺を白色で塗り、訪問済みの頂点に至る辺は黒のまま残す、というように全域木を作ると、黒色の辺が木が閉路を成すことはないようだ。
何となくうまくいく気がするけどちゃんと証明はできていないので、気になる人は公式Editorialを見た方が良い。
恐らく次数3が効いてくるのだろうが…。

vector<int> E[101010];
int M[1010][1010];
vector<int> ret;
int vis[1010];

class ColoringEdgesDiv1 {
	public:
	void dfs(int cur) {
		vis[cur]=1;
		FORR(e,E[cur]) if(vis[e]==0) {
			ret[M[cur][e]]=1;
			dfs(e);
		}
	}
	
	vector <int> findColoring(int n, vector <int> x, vector <int> y) {
		int i;
		ZERO(M);
		FOR(i,n) E[i].clear();
		FOR(i,x.size()) {
			E[x[i]].push_back(y[i]);
			E[y[i]].push_back(x[i]);
			M[x[i]][y[i]]=M[y[i]][x[i]]=i;
		}
		ZERO(vis);
		ret.resize(0);
		ret.resize(x.size());
		FOR(i,n) if(vis[i]==0) dfs(i);
		return ret;
	}
}

まとめ

こんなんでいいのかなぁ…。