C. Cut 'em all!

题目链接

Codeforces Round #484 (Div. 2)--C. Cut 'em all!

题解

中档题,题意大概是给定一个树,求最多可以删去多少条边满足剩下的每个联通分量均为偶数个节点。
emmm说实话我没想到什么特别的方法于是从叶子节点开始暴力……

代码

#include <bits/stdc++.h>
using namespace std;
int n,q,w;
map<int,int> a[100002];
bool boo[100002];
int link[100002][2];
map<int,map<int,int>> linknum;
int find(int from,int to){
    if (linknum[from][to]!=0)return linknum[from][to];
    if (a[to][0]==1)return 1;
    else {
        int num=1;
        for (int i=1;i<=a[to][0];i++){
            if (a[to][i]!=from)num+=find(to,a[to][i]);
        }
        linknum[from][to]=num;
        linknum[to][from]=num;
        return num;
    }
}
int main() {
    cin>>n;
    if (n%2==1){
        cout<<-1;
        return 0;
    }
    for (int i=1;i<=n-1;i++){
        cin>>q>>w;
        link[i][0]=q;
        link[i][1]=w;
        a[q][0]++;
        a[w][0]++;
        a[q][a[q][0]]=w;
        a[w][a[w][0]]=q;
    }
    int ans=0;
    int cache;
    for (int i=1;i<=n-1;i++){
        if (a[link[i][0]][0]==1||a[link[i][1]][0]==1)continue;
        else {
            if (find(link[i][0],link[i][1])%2==0)
            ans++;
            //cout<<link[i][0]<<' '<<link[i][1]<<endl;
        }
    }
    cout<<ans;
}

标签: dfs and similar, graphs, dp, greedy, trees

添加新评论