範例程式碼 uva1292

//uva1292
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_NODES 1500

int n; // number of nodes
int adj[MAX_NODES][MAX_NODES]; // adjacency matrix
int dp[MAX_NODES][2]; // dp table
int visited[MAX_NODES]; // visited array for DFS

void dfs(int node) {
    visited[node] = 1;
    dp[node][0] = 0; // No guard on this node
    dp[node][1] = 1; // Guard on this node

    for (int i = 0; i < n; i++) {
        if (adj[node][i] && !visited[i]) {
            dfs(i);
            dp[node][0] += dp[i][1]; // If no guard on node, children must have guards
            dp[node][1] += (dp[i][0] < dp[i][1]) ? dp[i][0] : dp[i][1]; // Place guard on node or child, whichever is minimal
        }
    }
}

int main() {
    while (scanf("%d", &n) == 1) {
        memset(adj, 0, sizeof(adj));
        memset(visited, 0, sizeof(visited));

        for (int i = 0; i < n; i++) {
            int node;
            scanf("%d:(", &node);
            int count;
            scanf("%d) ", &count);
            for (int j = 0; j < count; j++) {
                int conn;
                scanf("%d", &conn);
                adj[node][conn] = 1;
                adj[conn][node] = 1; // Because it is an undirected tree
            }
        }

        // Root the tree at node 0 (arbitrary choice since any node can be root in a tree)
        dfs(0);

        // The minimum number of guards needed is the minimum of having a guard or not on the root node
        int result = (dp[0][0] < dp[0][1]) ? dp[0][0] : dp[0][1];
        printf("%d\n", result);
    }
    return 0;
}