Codeforces Round #357 Div2 D: Gifts by the List

問題

Problem - D - Codeforces

解法

あるノード cur について考える。
cur および cur の子孫のうち、まだプレゼントを渡していない人がいるとする。この、「まだプレゼントを渡していない人」の中で cur に渡す人がいるなら、他の「まだプレゼントを渡していない人」は cur より上の人にプレゼントを渡す事ができないので、全員が cur に渡すことになる。これを dfs で考えていけば良い。

コード

public class D {
  private static class Task {
    ArrayList<Integer>[] g;
    ArrayList<Integer> ans = new ArrayList<>();
    boolean ok = true;
    int[] appear, a;

    int dfs(int cur) {
      int children = 0;// cur あるいは cur の祖先にプレゼントしてくれる子供の数
      for (int r : g[cur]) children += dfs(r);
      appear[a[cur]]++;
      children++;

      // cur にプレゼントする人の数が0ならそのまま上る
      if (appear[cur] == 0) return children;

      // cur を超えてプレゼントしようとする人がいるなら無理
      if (children > appear[cur]) {
        ok = false;
        return 0;
      }

      // 今抱えている children は全員 cur にプレゼントする
      ans.add(cur);
      return 0;
    }

    void solve(FastScanner in, PrintWriter out) {
      int n = in.nextInt();
      int m = in.nextInt();
      g = new ArrayList[n + 1];
      for (int i = 0; i < n + 1; i++) g[i] = new ArrayList<>();
      int[] parent = new int[n + 1];
      for (int i = 0; i < m; i++) {
        int x = in.nextInt(), y = in.nextInt();
        parent[y] = x;
        g[x].add(y);
      }

      a = new int[n + 1];
      for (int i = 0; i < n; i++) a[i + 1] = in.nextInt();

      appear = new int[n + 1];
      for (int i = 1; i <= n; i++) if (parent[i] == 0) dfs(i);

      if (!ok) {
        out.println(-1);
      } else {
        out.println(ans.size());
        ans.forEach(out::println);
      }
    }
  }
}