NTPFECT - Đại diện hoàn hảo
Tác giả: khuc_tuan
Ngôn ngữ: C++
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
int n, res;
vector <int> ke[1010];
int state[1010];
void dfs(int i, int fi) {
bool ok = false, co = false;
for(int k=0;k<ke[i].size();++k) {
int j = ke[i][k];
if(j != fi) {
dfs(j, i);
if(state[j] == 0) ok = true;
if(state[j] == 2) co = true;
}
}
if(ok) state[i] = 2, ++res;
else if(co) state[i] = 1;
}
int main() {
while(true) {
scanf("%d", &n);
if(n == 0) break;
for(int i=1;i<=n;++i) ke[i].resize(0);
for(int i=1;i<n;++i) {
int u, v;
scanf("%d%d", &u, &v);
ke[u].push_back(v);
ke[v].push_back(u);
}
memset( state, 0, sizeof(state));
res = 0;
dfs(1, -1);
if(state[1] == 0) ++res;
printf("%d\n", res);
}
return 0;
}