Senの競技プログラミング備忘録

こけた問題を自分用の解説で載せる。けんちょんさんのブログを目指したい。質的にも量的にも。こけた問題だけに限定するけど

Codeforces Round #544 (Div. 3) - F2. Spanning Tree with One Fixed Degree

codeforces.com

概要

N頂点M辺の無向グラフが与えられる。次の条件を満たす全域木を1つ出力せよ。
全域木を構成する辺のうち、頂点1と連結してる辺はD本である。

制約: 1 <= N <= 2 * 10^5, N - 1 <= M <= min(2 * 10^5, N * (N - 1) / 2)
1 <= D <= N

ACするまで

1. ひとまず適当にグラフを書いてみると、頂点1から出てるいくつかの辺は、また頂点1に戻りうるとわかる。
2. そのような辺の集合は、最低限を考えると1本だけ残して、それ以外を使わないとできる。そして使う本数も1本単位で調節できる。(詳しいのは考察で)
3. うまい実装方針を考えて、コンパクトにまとまるように書く。
4. AC!

考察

頂点1から出てる辺について、紙で実験すると次の事実が分かる。文字ではどうしても伝わりづらいので、一度紙に適当なグラフを書いてみることをお勧めする。


頂点1から出てくる辺を通ってたどりつける頂点で、往路とは異なるルートでまた1に帰れるようなものは、その頂点1から出る辺によってつながっているといえる。この時に、頂点1から出るときと頂点1に帰るときに使う2本の辺は、2本以上なのもありうる。(下の具体例参照、3本つながっていて、そのうちの1本を行き、また別の1本を帰りに使い、最後の1本を使わないなどでもよい。)
この時、その往路と復路に使われる可能性のある辺のうち、最低1本でも使えば、頂点1から、そのような頂点へたどりつけて(これは部分全域木)、しかも使う本数も1本、2本...と自由に決められる。(なぜなら最低1本でそれらの頂点とつながるとわかっているので、2本、3本とつながりを増やしても当然つながるため)

この事実をもとに考えると、
1から出るすべての辺をこの考えで、いくつかの辺の集合に分けてると、集合1つに最低1から1本の辺を出す必要があるので、全域木を作るために必要な最低限の辺は、(集合の数)だけ必要となる。
必要最低限の辺を張り終えたら、先ほど述べたように、辺の集合のうち2本以上を含むものの中から適当に辺を選べば、出次数Dは達成できる。もちろん、もともと頂点1の出次数より大きいDは作れないが。

よって、辺を集合に分解して、頂点1から伸びる辺を指定してからUnion_Findなどで全域木を構築すればよい。

実装のテクニックとしては、from_0のような2次元vectorをもって、DFS関数に参照を渡して、DFS関数内で頂点1(コード内では0-idxしてるので、頂点0になってる)へ戻れたのならば、集合に含まれた辺として検知できる。

vector<vector<int>> from_0;//from_0[i][j] := i番目のグループからに属してる、j番目の辺は、1->from_0[i][j]へ向かう。
	visited[0] = true;
	for (int i = 0; i < E[0].size(); i++) {//1度のDFSで、集合内のすべての辺とそこからいける頂点を調べられる。
		int nxt = E[0][i];
		if (!visited[nxt]) {
			vector<int> tmp;
			tmp.push_back(nxt);
			dfs(nxt, 0, tmp);
			from_0.push_back(tmp);
		}
	}

//dfs関数
void dfs(int now, int bef, vector<int>& to0) {
	visited[now] = true;
	for (int i = 0; i < E[now].size(); i++) {
		int nxt = E[now][i];
		if (nxt == bef)continue;
		if (!visited[nxt]) {
			dfs(nxt, now, to0);
		}
		if (nxt == 0) {
			to0.push_back(now);
		}
	}
}

ACソースコード
Submission #70276520 - Codeforces

一言

直感的にわかる証明や定理でも、人に説明する文章を書くときにすごく頭と時間を使う。その分頭が整理されるけど。