Codeforces #698 Div1 : D. Nezzar and Hidden Permutations

これコードも短くないのに、妙にAC数多いな。
https://codeforces.com/contest/1477/problem/D

問題

正整数Nと、M個の整数対(L[i],R[i])が与えられる。
以下の条件のもと、スコアを最大化するPermutation P,Qを構築せよ。

• PもQも1～NのPermutationである。
• 各整数対(L[i],R[i])に対し、P[L[i]]とP[R[i]]の大小関係と、Q[L[i]]とQ[R[i]]の大小関係は一致しなければならない。
  • 1つでも一致しない場合、スコアは-1である。
  • すべて大小関係を満たした場合、P[i]≠Q[i]であるiの個数がスコアとなる。

解法

N頂点のグラフで、(L[i],R[i])間に無向辺を張ったものを考える。
もし次数(N-1)辺の点vがあれば、そこは大小関係から値が確定するので、その場合P[v]=Q[v]であることを許容し、その点を取り除く。

残ったN点について、必ずスコアをN得られる構成が組める。
このグラフの補グラフを考え、これをいくつかのウニ型グラフに分解する。

ウニの中心uと周辺の点vに対し、P[u]とP[v]の大小関係はどうでも良いことになる。
これらの点に1～Kの値を振るとき、

• P[u]=1、P[v]=2～K
• Q[u]=K、Q[v]=1～(K-1)

とすれば問題ない。

あとは補グラフをウニに分解していけばよい。
これはSpanning Treeを長さ2以下の連結成分に分解していくとよい。

int T,N,M;

set<int> E[505050],F[505050];
int P[505050],Q[505050];
int vis[505050];
int cv=0;
vector<int> C[505050];

int dfs(int cur) {
	vis[cur]=1;
	FORR(e,F[cur]) if(vis[e]==0) {
		int ret=dfs(e);
		if(ret==0) Q[cur]=Q[e]=cur;
	}
	return Q[cur]>=0;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d",&T);
	while(T--) {
		scanf("%d%d",&N,&M);
		FOR(i,N+1) E[i].clear(),C[i].clear(),P[i]=Q[i]=-1,F[i].clear(),vis[i]=0;
		
		FOR(i,M) {
			scanf("%d%d",&x,&y);
			E[x-1].insert(y-1);
			E[y-1].insert(x-1);
		}
		set<int> L;
		FOR(i,N) {
			C[E[i].size()].push_back(i);
			L.insert(i);
		}
		x=N;
		while(x&&C[x-1].size()) {
			y=C[x-1][0];
			P[y]=Q[y]=x;
			vis[y]=1;
			L.erase(y);
			x--;
			FOR(i,x+1) C[i].clear();
			FORR(e,E[y]) {
				E[e].erase(y);
				C[E[e].size()].push_back(e);
			}
		}
		if(L.size()) {
			
			while(L.size()) {
				queue<int> QU;
			
				QU.push(*L.begin());
				L.erase(L.begin());
				while(QU.size()) {
					x=QU.front();
					QU.pop();
					vector<int> del;
					FORR(l,L) {
						if(E[x].count(l)==0) {
							F[x].insert(l);
							F[l].insert(x);
							QU.push(l);
							del.push_back(l);
						}
					}
					FORR(d,del) L.erase(d);
				}
			}
			FOR(i,N) if(vis[i]==0&&F[i].size()) {
				x=dfs(i);
				if(x==0) Q[i]=Q[*F[i].begin()];
			}
			FOR(i,N+1) C[i].clear();
			FOR(i,N) if(P[i]!=Q[i]&&Q[i]!=i) C[Q[i]].push_back(i);
			x=1;
			FOR(i,N) if(C[i].size()) {
				FOR(j,C[i].size()) {
					P[C[i][j]]=x+j;
					Q[C[i][j]]=x+j+1;
				}
				P[i]=x+C[i].size();
				Q[i]=x;
				x+=C[i].size()+1;
			}
		}
		
		
		FOR(i,N) _P("%d ",P[i]);
		_P("\n");
		FOR(i,N) _P("%d ",Q[i]);
		_P("\n");
		
		
	}
}

まとめ

これは考察も実装も割としんどいな。