CSAcademy Round #38 : F. Tree Antichain (Hard)

これは解けてよかった。
https://csacademy.com/contest/round-38/task/tree-antichain-hard/

問題

1～Nのラベル付き頂点からなる木を成すグラフが与えられる。

ここで、[1,N]のPermutationのうち、数列中で隣接する要素がグラフ中で隣接しないものであり、その中で辞書順最小のものを求めよ。

解法

辞書順最小の構成を求める問題なので、数列の先頭から要素を定めていこう。
さて、数列を途中まで作ったとき、残された頂点ではどうやっても条件を満たせなくなるようなものを考える。
それは、残された頂点が１つの連結成分を成し、かつ直径が２か３の場合である。
こうなるといずれどこかで隣接した頂点を連続して数列に含む場所が出てしまう。

逆を言えば、以下を満たす最小の要素を適宜選んでいけばよい。

• 直前に選んだ要素とグラフ中で隣接しない
• その要素を取り除いても、残された頂点は「１つの連結成分を成し、かつ直径が２か３の場合」とならない。

最後の条件を高速に求める方法だが、この状態というのは最多の辺をもつ頂点が他の全頂点と隣接している状態に等しい。
よって最多の辺をもつ頂点さえ管理しておけばよい。

int T;
int N;
set<int> E[101010];
int num[101010];
set<pair<int,int>> NS;

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) E[i].clear();
		FOR(i,N-1) {
			cin>>x>>y;
			E[x-1].insert(y-1);
			E[y-1].insert(x-1);
		}
		NS.clear();
		set<int> cand,ng;
		vector<int> ret;
		FOR(i,N) {
			NS.insert({E[i].size(),i});
			cand.insert(i);
		}
		
		FOR(i,N) {
			x = -1;
			int left=N-i;
			FORR(c,cand) {
				if(ng.count(c)) continue;
				if(E[c].size()+1==left && left!=1) continue;
				if(E[c].size()>1 || left==1) {
					x=c;
					break;
				}
				
				FORR(e,E[c]) {
					NS.erase({E[e].size(),e});
					E[e].erase(c);
					NS.insert({E[e].size(),e});
				}
				NS.erase({E[c].size(),c});
				
				auto mo=NS.rbegin();
				int ok=!(mo->first==left-2 && left>=3);
				
				NS.insert({E[c].size(),c});
				FORR(e,E[c]) {
					NS.erase({E[e].size(),e});
					E[e].insert(c);
					NS.insert({E[e].size(),e});
				}
				
				if(ok) {
					x=c;
					break;
				}
			}
			if(x==-1) {
				_P("-1\n");
				goto out;
			}
			cand.erase(x);
			ret.push_back(x);
			ng.clear();
			NS.erase({E[x].size(),x});
			FORR(e,E[x]) {
				NS.erase({E[e].size(),e});
				E[e].erase(x);
				ng.insert(e);
				NS.insert({E[e].size(),e});
			}
		}
		
		
		FOR(i,N) _P("%d%c",ret[i]+1,(i==N-1)?'\n':' ');
		out:;
	}
}

まとめ

「１つの連結成分を成し、かつ直径が２か３の場合」の高速な判定でしばらく唸っていたが、最終的に解けて良かった。