python/TangDou/AcWing/Tree/323.cpp

#include <bits/stdc++.h>
using namespace std;

const int N = 1510, M = N << 1;
int f[N][2];

// 邻接表
int e[M], h[N], idx, ne[M];
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
/**
 集合：    以结点i为 根节点 的子树，在 i 上放置哨兵(1) 和不放哨兵(0) 的方案
 状态表示： 方案中，放置的哨兵数量 最少
 状态计算：
 */
int in[N]; // 入度

void dfs(int u) {
    for (int i = h[u]; ~i; i = ne[i]) { // 遍历每一条出边
        int v = e[i];
        dfs(v);
        // 状态转移方程
        f[u][0] += f[v][1];               // 节点u不放置哨兵，那么一定要从某一邻接节点放置哨兵
        f[u][1] += min(f[v][0], f[v][1]); // 如果节点u放置了哨兵，那么邻接节点可以选择放置或者不放置
    }
    // u节点选中
    f[u][1] += 1;
}

int main() {
    // n组数据
    int n;

    while (~scanf("%d", &n)) {            // 不断读入数据
        memset(h, -1, sizeof h), idx = 0; // 多组数据，清空邻接表
        memset(in, 0, sizeof in);         // 清空入度数组
        // dp数组也清空一下
        memset(f, 0, sizeof f);
        // n个节点
        for (int i = 1; i <= n; i++) {
            int x, m;
            scanf("%d:(%d)", &x, &m); // scanf可以按格式读入数据
            while (m--) {
                int y;
                scanf("%d ", &y);
                // 添加一条x->y的有向边
                // 数据样例：1出发可以到达2,3;说明是有向图
                add(x, y);
                // 记录y的入度，用于找根节点
                in[y]++;
            }
        }
        // 有向图，找根
        int root = 0;
        while (in[root]) root++;

        // 从根开始
        dfs(root);

        // 输出 两个结果取个 min
        printf("%d\n", min(f[root][0], f[root][1]));
    }
    return 0;
}