即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

偶数树 并查集

编程语言 xinxiaxindong 18℃ 0评论
本文目录
[隐藏]

1.Description

给你一棵有n个节点的树(一个无环简单图),节点序号为1~n,根节点为1。


请你找出一个最大的整数k,表示从这棵树上断掉k条边使其所有的子树的节点数都为偶数。

2.Input

第一行输入两个整数N,M。表示这棵树有N个节点和M条边。


接下来有M行,每行输入两个整数u,v,表示u节点和v节点间有一条边相连。

数据保证:2 ≤ n ≤ 100,并且所有的节点都在一棵树上。


输入的树总能被分解为包含偶数个节点的子树

3.Output

输出最多可以移除掉边的数量。

4.Sample Input

10 9


2 1


3 1


4 3


5 2


6 1


7 2


8 6


9 8


10 8

5.Sample Output

2

5.1.Hint

样例中移除掉(1,3)(1,6)两条边满足条件。


原始树:这里写图片描述

分解的树:这里写图片描述

5.2.题意

5.3.题解:

n为奇数的情况应该是不存在的 所以根节点1的子节点数一定是偶数(前提 记录初始值为1所以结果减一


思路也不是很难想 就是想要用并查集实现这点不容易 多想想应该可以写出来吧 (转化为有向图 序号统一由大指小)


把每个节点视为根节点 统计其子节点个数 那么要断掉的就是一个子节点个数(包括它自己)是否是偶数 如果是那么它和它的这一堆子节点便可以作为一个整体 然后便可以和它指向的点断开啦 经过这么操作 即可得到最多可以得出的数量啦(遍历了所有可能去断的节点) 又因为根节点 1 无指向节点而它的子节点个数(包括它自己)一定是偶数 所以结果要减 1

5.4.AC代码

#include 
#include 
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 (xelse {
            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;
}

转载请注明:CodingBlog » 偶数树 并查集

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情