Codeforces Round #318 Div1 C: Bear and Drawing
解法
頂点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(); } }