yukicoder : No.3552 Triangular Coloring

これは割とすんなり解けた。
https://yukicoder.me/problems/no/3552

問題

N点M辺の平面グラフが与えられる。
このグラフは以下のように構築される。

• 初期状態は３点の完全グラフである。
• グラフ内の三角形の面を選び、その中に１点追加して、三角形を成す３点それぞれと結ぶ、というのをN点になるまで繰り返す。

このグラフを四色で彩色せよ。

解法

すでに４色で彩色されているグラフに対し、構築手順の後者を行う場合、追加した点は三角形を成す３点と異なる色を塗ればよい。
よって、グラフの構築手順を復元できれば彩色は容易。

そのために、グラフの構築を逆順に復元しよう。
これは次数３の点を順次選んで取り除いていけばよい。

int N,M;
set<int> E[202020];

vector<vector<int>> V;
int C[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		E[x-1].insert(y-1);
		E[y-1].insert(x-1);
	}
	queue<int> Q;
	FOR(i,N) if(E[i].size()==3) Q.push(i);
	while(Q.size()) {
		int cur=Q.front();
		Q.pop();
		if(E[cur].size()!=3) continue;
		vector<int> A={cur};
		FORR(e,E[cur]) {
			A.push_back(e);
			E[e].erase(cur);
			if(E[e].size()==3) Q.push(e);
		}
		V.push_back(A);
		E[cur].clear();
	}
	x=0;
	FOR(i,N) if(E[i].size()) {
		C[i]=x++;
	}
	assert(x);
	reverse(ALL(V));
	FORR(v,V) {
		C[v[0]]=6-C[v[1]]-C[v[2]]-C[v[3]];
	}
	cout<<"Yes"<<endl;
	FOR(i,N) cout<<C[i]+1<<" ";
	cout<<endl;
	
}

まとめ

ここらへんはサクサク解けて良かったね。