本文共 694 字，大约阅读时间需要 2 分钟。

题意

去除尽可能多的边,使得剩下的连通块里点的个数都为偶数

思路

n为奇数直接输出-1

偶数的话从一个点开始递归找节点的子节点的数目(包含本身),如果是偶数则可以直接去除,因为只有n-1个边,也就是说剩下的一定是一个偶数的连通块

最后我们需要减1，因为本身这棵树如果是偶数的话也会算进去一次

code

#include
   
    #define endl '\n'using namespace std;const int maxn=1e5+5;vector
    
      G[maxn];int n;int cnt;int dfs(int u,int fa){
       int sum=1;    for(auto v:G[u]){
           if(v==fa) continue;        sum+=dfs(v,u);    }    if(sum%2==0) cnt++;    return sum;}int main(){
       ios::sync_with_stdio(false);    cin.tie(0);    cin>>n;    for(int i=1;i<=n-1;i++){
           int u,v;        cin>>u>>v;        G[u].push_back(v);        G[v].push_back(u);    }    cnt=0;    dfs(1,-1);    if(n&1){
           cout<<-1<
    
   

学如逆水行舟，不进则退

转载地址：https://chocolate.blog.csdn.net/article/details/104146365 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！