範例程式碼 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;
}