WUPC 2019 : C - Permutation City

ちょっと戸惑った。
https://atcoder.jp/contests/wupc2019/tasks/wupc2019_c

問題

頂点に1～Nのラベルを振られた連結無向グラフが与えられる。
1～NのPermutationのうち、i番とP[i]番の頂点の距離が1か2となるものを１つ構成せよ。

解法

入力は木ではないが、一部の辺を無視して木とみなして処理しても問題ない。（距離２となる予定が、無視した辺の存在によって１となりうるだけである）
以下の通りDFS順に処理していこう。

頂点vを処理するとき、その子頂点群のうち未処理のものがあれば、２つずつペアにしていく。
vの子頂点c1,c2同士は距離2なので、それらを互いにペアにしてP[c1]=c2, P[c2]=c1とするとこれらは条件を満たす。
もし子頂点が１個余った場合、vとペアにしよう。
もし子頂点が余らない場合、vは未処理の点となり、さらにその親頂点の処理過程で兄弟または親頂点とペアになる。

ただ、全体の頂点数が奇数のとき、根頂点が１個余る。
とはいえ、この時の子頂点は、孫頂点または兄弟の頂点とペアになっているはずであり、それらはいずれも根頂点から距離が２以下である。
よってその場合は３つをトリオにして組み合わせればよい。

int N,M;
vector<int> E[202020];
vector<int> C[202020];
int P[202020];
int vis[202020];
int NC[202020];
int PA[202020];
int le[202020];

int dfs(int cur,int par) {
	vis[cur]=1;
	P[cur]=par;
	NC[cur]=1;
	FORR(e,E[cur]) if(vis[e]==0) {
		NC[cur]+=dfs(e,cur);
		C[cur].push_back(e);
	}
	return NC[cur];
}

int dfs2(int cur) {
	int ano=-1;
	
	FORR(e,C[cur]) {
		dfs2(e);
		if(le[e]>=0) {
			if(ano>=0) {
				PA[ano]=le[e];
				PA[le[e]]=ano;
				ano=-1;
			}
			else {
				ano=le[e];
			}
		}
	}
	
	if(ano==-1) {
		le[cur]=cur;
	}
	else {
		PA[cur]=ano;
		PA[ano]=cur;
		le[cur]=-1;
	}
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	
	dfs(0,0);
	
	dfs2(0);
	if(le[0]==0) {
		x=C[0][0];
		y=PA[x];
		PA[0]=x;
		PA[x]=y;
		PA[y]=0;
	}
	FOR(i,N) cout<<PA[i]+1<<" ";
	cout<<endl;
	
}

まとめ

木じゃなくてもいいのが面白いところではあるけど、この問題だと皆すぐ木で解く方向に到達しちゃいそうね。