Description
给你一棵有n个节点的树（一个无环简单图），节点序号为1~n，根节点为1。 请你找出一个最大的整数k，表示从这棵树上断掉k条边使其所有的子树的节点数都为偶数。
第一行输入两个整数N，M。表示这棵树有N个节点和M条边。 接下来有M行，每行输入两个整数u，v，表示u节点和v节点间有一条边相连。
数据保证：2 ≤ n ≤ 100，并且所有的节点都在一棵树上。 输入的树总能被分解为包含偶数个节点的子树
Output
输出最多可以移除掉边的数量。
10 9 2 1 3 1 4 3 5 2 6 1 7 2 8 6 9 8 10 8
Sample Output
2
Hint
样例中移除掉（1，3）（1，6）两条边满足条件。 原始树：
分解的树：
题意
题解：
n为奇数的情况应该是不存在的 所以根节点1的子节点数一定是偶数（前提 记录初始值为1所以结果减一 思路也不是很难想 就是想要用并查集实现这点不容易 多想想应该可以写出来吧 (转化为有向图 序号统一由大指小) 把每个节点视为根节点 统计其子节点个数 那么要断掉的就是一个子节点个数（包括它自己）是否是偶数 如果是那么它和它的这一堆子节点便可以作为一个整体 然后便可以和它指向的点断开啦 经过这么操作 即可得到最多可以得出的数量啦（遍历了所有可能去断的节点） 又因为根节点 1 无指向节点而它的子节点个数（包括它自己）一定是偶数 所以结果要减 1
AC代码
#include <cstdio>
#include <algorithm>
using namespace std;
int par[
110],rkan[
110];
int n,m;
void set_init(){
for (
int i =
1; i <= n; ++i){
par[i] = i;
rkan[i] =
1;
}
}
int find(
int x){
if (x == par[x])
return x;
rkan[par[x]]++;
return find(par[x]);
}
void set_unit(
int x,
int y){
int fx = find(x);
int fy = find(y);
if (fx!=fy){
if (x<y){
par[y] = x;
rkan[x]++;
}
else {
par[x] = y;
rkan[y]++;
}
}
}
int main(){
scanf(
"%d%d",&n,&m);
set_init();
int a,b;
for (
int i =
0; i < m; ++i){
scanf(
"%d%d",&a,&b);
set_unit(a,b);
}
int ans =
0;
for (
int i =
1; i <= n; ++i){
if (rkan[i]%
2==
0){
ans++;
}
}
printf(
"%d\n",ans-
1);
return 0;
}
