AtCoder ABC #244 : G - Construct Good Path

こっちは定番かな…。
https://atcoder.jp/contests/abc244/tasks/abc244_g

問題

連結無向グラフが与えられる。
各頂点に対する到達回数の偶奇が指定されるので、その条件を満たすパスを1つ構成せよ。

解法

まずグラフの全域木を考え、根付き木とみなして、DFSで根から全頂点をたどることを考える。
現在の頂点Vから子頂点Cに遷移して戻るとき、仮に子頂点Cの到達回数の偶奇が合わないとする。
その場合、V→C→Vと遷移して、C・Vの到達回数を1回増やそう。
これでCの到達回数は帳尻があう。

こうすると、根頂点を始点及び終点とするパスができる。
最後根頂点の偶奇が合わない場合、始点か終点のいずれかを削ればよい。

template<int um> class UF {
	public:
	vector<int> par,rank,cnt;
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit(int num=um) {int i; FOR(i,num) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<101010> uf;

int N,M;
vector<int> E[101010];
string S;

vector<int> ret;

void add(int cur) {
	S[cur]^=1;
	ret.push_back(cur);
}

void dfs(int cur,int pre) {
	add(cur);
	FORR(e,E[cur]) if(e!=pre) {
		dfs(e,cur);
		add(cur);
		if(S[e]) {
			add(e);
			add(cur);
		}
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		x--,y--;
		if(uf[x]!=uf[y]) {
			uf(x,y);
			E[x].push_back(y);
			E[y].push_back(x);
		}
	}
	cin>>S;
	FORR(c,S) c-='0';
	
	dfs(0,0);
	if(S[0]) ret.pop_back();
	cout<<ret.size()<<endl;
	FORR(r,ret) cout<<r+1<<" ";
	cout<<endl;
	
}

まとめ

UFで全域木求めたけど、ループしないようDFS順で探索打ち切るだけでも良かったかな。