Codeforces #259 Div1 C. Little Pony and Summer Sun Celebration

本番割とすんなり思いつけて良かった。
http://codeforces.com/contest/453/problem/C

問題

N点M辺のグラフがある。
またここで各点の到達回数のパリティX[i]が与えられる。

このグラフにおいて、任意の始点から初めて、4N回以内で辺をたどっていくつかの点を訪れるパスを考えるとき、各頂点の到達回数のパリティがX[i]と一致するようなものがあればそれを答えよ。

解法

パスは1回しかたどれないので、まず非連結な複数頂点にパリティがある場合は不可なのは明らか。
よって以後は連結した頂点群1個の場合を考える。

初期状態で各点のパリティX[i]を設定し、何度か頂点をたどって全パリティを0にする手段を考える。
ここで「自分の(未到達)の子以降の子孫はパリティを0にする」というDFSを行えばよい。
すると今の自ノードが各子頂点にDFSすると、孫以降はすべてパリティは0になっているはずである。
もし子頂点にまだパリティが残っていれば自ノード→子→自ノードという往復移動を1回行えばよい。

DFSの開始ノードのパリティが残る場合があるが、DFS処理におけるパスの先頭はかならず開始ノードなので、それを取り除けばよい。

木の探索なので使用する辺はN-1本であり、各辺の移動回数は4回以下なので全体のパスも4N以下になる。

int N,M;
int P[100001],HP[100001];
vector<int> E[100001];
class UF {
	public:
	static const int ufmax=100002;
	int ufpar[ufmax],ufrank[ufmax],ufcnt[ufmax];
	UF() { init();}
	void init(){int i; FOR(i,ufmax) { ufpar[i]=i; ufrank[i]=0; ufcnt[i]=1; } }
	int find(int x) {	return (ufpar[x]==x)?(x):(ufpar[x] = find(ufpar[x]));}
	int operator[](int x) {return find(x);}
	int count(int x) {return ufcnt[x];}
	void unite(int x,int y) {
		x = find(x); y = find(y);
		if(x==y) return;
		if(ufrank[x]<ufrank[y]) ufpar[x]=y, ufcnt[y]+=ufcnt[x];
		else {ufpar[y]=x; ufcnt[x]+=ufcnt[y]; if(ufrank[x]==ufrank[y]) ufrank[x]++;}
	}
};

int vis[100001];
vector<int> V;

int dfs(int cur) {
	int i,r,num=0;
	vis[cur]=1;
	
	V.push_back(cur);
	P[cur]^=1;
	
	FOR(i,E[cur].size()) {
		int tar=E[cur][i];
		if(vis[tar]) continue;
		r=dfs(tar);
		V.push_back(cur);
		P[cur]^=1;
		if(r) {
			V.push_back(tar);
			V.push_back(cur);
			P[cur]^=1;
		}
	}
	return P[cur];
}

void solve() {
	int f,i,j,k,l,x,y;
	UF uf;
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
		uf.unite(x-1,y-1);
	}
	FOR(i,N) cin>>P[i];
	
	FOR(i,N) HP[uf[i]] += P[i];
	x=0,y=-1;
	FOR(i,N) if(HP[i]) x++, y=i;
	if(x==0) return _P("0\n");
	if(x>1) return _P("-1\n");
	
	x=dfs(y);
	if(x) V.erase(V.begin());
	_P("%d\n",V.size());
	FOR(i,V.size()) _P("%d ",V[i]+1);
	_P("\n");
	
}

まとめ

こういう問題は割と好き。