TopCoder SRM 821 : Div2 Hard ConnectTheWorld

というわけで久々のDiv2 Hard単独の問題。
https://community.topcoder.com/stat?c=problem_statement&pm=17352

問題

無向グラフが与えられる。
このグラフにいくつか辺を加え、グラフを連結にしたい。
ただし、初期状態で最大の次数を持つ頂点より、次数が多い頂点が登場するのは不可とする。

解法

連結成分毎に、後何本辺を追加できるかをカウントしよう。
その数が多い2成分を選択し、辺で結ぶことを繰り返して最終的に1つの成分にできるかチェックすればよい。

vector<int> E[96];
vector<int> cand[96];
int vis[96];


class ConnectTheWorld {
	public:
	int MAX;
	void dfs(int cur,int start) {
		if(vis[cur]) return;
		vis[cur]=1;
		int i;
		FOR(i,MAX-E[cur].size()) cand[start].push_back(cur);
		FORR(e,E[cur]) dfs(e,start);
	}
	
	vector <string> connect(vector <string> terminalA, vector <string> terminalB, vector <string> isolated) {
		map<string,int> M;
		MAX=0;
		FORR(a,terminalA) M[a]++;
		FORR(a,terminalB) M[a]++;
		FORR(a,isolated) M[a]=0;
		
		vector<string> C;
		map<int,int> num;
		FORR(m,M) {
			if(m.second) num[m.second]++;
			MAX=max(MAX,m.second);
			M[m.first]=C.size();
			E[M[m.first]].clear();
			cand[M[m.first]].clear();
			C.push_back(m.first);
		}
		cout<<MAX<<endl;
		int i;
		FOR(i,terminalA.size()) {
			E[M[terminalA[i]]].push_back(M[terminalB[i]]);
			E[M[terminalB[i]]].push_back(M[terminalA[i]]);
		}
		
		ZERO(vis);
		priority_queue<pair<int,int>> con;
		FOR(i,C.size()) if(vis[i]==0) {
			dfs(i,i);
			con.push({cand[i].size(),i});
		}
		
		vector<string> R;
		while(con.size()>1) {
			int x=con.top().second;
			con.pop();
			int y=con.top().second;
			con.pop();
			if(cand[x].empty()||cand[y].empty()) return {};
			R.push_back(C[cand[x].back()]);
			R.push_back(C[cand[y].back()]);
			cand[x].pop_back();
			cand[y].pop_back();
			FORR(a,cand[y]) cand[x].push_back(a);
			con.push({cand[x].size(),x});
		}
		
		return R;
	}
}

まとめ

なんでわざわざ頂点を番号でなく文字列にしたんだろう…。
現実的な問題であることを強調したいのかもしれないけど、本質的でない部分で手間がかかってイライラする効果の方が大きい…。