Codeforces Round #318 Div1 C: Bear and Drawing

問題

codeforces.com

解法

頂点iに接続している頂点vについて考える。

  • vが葉に接続している一本道の途中にある頂点であれば、葉の一部と考えれば良い。
  • i以外にvが持っている葉が2枚以下であれば、vはiの対岸の行に収めることができる。
  • vがもつ葉が3枚以上、もしくは、vが葉でない頂点をもつ場合、vはiと同じ行に収めることになる。
    • 対岸の行に収めても、その葉でiの行を塞がれてしまうので同じことになる。
  • iと同じ行にはiから2つまでしか頂点を引けないので、3つ以上接続している場合にはNoを返す。

コード

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

	private ArrayList<ArrayList<Integer>> graph;
	private boolean[] delete;
	private int[] ignorableLegs;

	public void solve() {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		graph = new ArrayList<>();
		for (int i = 0; i < N; i++) {
			graph.add(new ArrayList<Integer>());
		}
		delete = new boolean[N];
		ignorableLegs = new int[N];

		for (int i = 0; i < N - 1; i++) {
			int a = scanner.nextInt() - 1;
			int b = scanner.nextInt() - 1;
			graph.get(a).add(b);
			graph.get(b).add(a);
		}
		scanner.close();

		for (int i = 0; i < N; i++) {
			if (graph.get(i).size() == 1) {
				// 次数が1の頂点(葉になっている)から調べ始める
				dfs(i, -1);
			}
		}
		for (int i = 0; i < N; i++) {
			for (int v : graph.get(i)) {
				if (delete[v]) {
					// iがもつ葉の数を数えておく
					ignorableLegs[i]++;
				}
			}
		}

		// 足は2本までなら水平方向に収まるので無視できる
		for (int i = 0; i < N; i++) {
			ignorableLegs[i] = Math.min(ignorableLegs[i], 2);
		}

		for (int i = 0; i < N; i++) {
			if (delete[i]) {
				// 削除された頂点ならスルー
				continue;
			}
			int cnt = 0;
			for (int v : graph.get(i)) {
				// vの足が3本以上あるか、足以外に生えている場合は、iに対して垂直方向に収めることができない
				if (!delete[v] && graph.get(v).size() - 1 > ignorableLegs[v]) {
					cnt++;
				}

				// 垂直方向に収まらない枝が2本までなら、iの両側に置けば良いが、3本以上だと置くことができない
				if (cnt > 2) {
					System.out.println("No");
					return;
				}
			}
		}
		System.out.println("Yes");
		return;

	}

	private void dfs(int now, int from) {
		/*
		 * 葉から登って行き, 調べている頂点が葉へと続く1本道の途中であればdeleteする
		 */
		if (graph.get(now).size() > 2) {
			return;
		}

		/*
		 * 頂点の次数が2以下なら, nowはparentを除いて子を1つだけもつ頂点である. この頂点は葉につながる1直線の枝の途中なので,
		 * 消していく
		 */
		delete[now] = true;
		for (int upper : graph.get(now)) {
			if (upper != from) {
				dfs(upper, now);
			}
		}
	}

	public static void main(String[] args) {
		new Main().solve();
	}
}