Codeforces --- 982C Cut 'em all! DFS加贪心-白红宇

Codeforces --- 982C Cut 'em all! DFS加贪心

阅读量：5288 次

发布时间：2019-06-14

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

题目链接：

输入输出：

Examples

inputCopy

2 4

4 1

3 1

outputCopy

inputCopy

1 2

1 3

outputCopy

-1

inputCopy

7 1

8 4

8 10

4 7

6 5

9 3

3 5

2 10

2 5

outputCopy

inputCopy

1 2

outputCopy

Note

In the first example you can remove the edge between vertices 11 and 44. The graph after that will have two connected components with two vertices in each.

In the second example you can't remove edges in such a way that all components have even number of vertices, so the answer is −1

题目大意：

这道题其实题意很简单，给你一棵树，让你删边，然后得到的子树节点个数要是偶数。

而边的个数在离散数学里定义是 m = n-1，这个在建树的时候需要注意！

DFS的作用是统计这个节点连接的节点的个数，具体实现在代码中有注释。

下面是AC代码：

#include 
      
       #include 
       
        #include 
        
         #define pb push_back#include 
         
          using namespace std;const int MX = 1e5+10;int vis[MX], sum[MX];int n;vector
          
            G[MX];int dfs(int x){    for(int i = 0; i < G[x].size(); ++i)    {        int u = G[x][i];        if(!vis[u])        {            vis[u] = 1; // 经过的点先标记一下            sum[x] += dfs(u); //沿着点DFS            vis[u] = 0; // 回溯        }    }    sum[x]++; // 经过一个点则需要加一    return sum[x];}int main(){    int ans = 0;    memset(vis, 0, sizeof(vis));    memset(sum, 0, sizeof(sum));    scanf("%d", &n);    for(int i = 1; i <= n-1; ++i) // 建树初始化m = n-1    {        int u, v;        scanf("%d%d", &u, &v);        G[u].pb(v);        G[v].pb(u); // 无向图！    }    if(n%2) //节点为奇数则不可能都分为偶数节点的连通图    {        printf("-1\n");        return 0;    }    vis[1] = 1; // 初始节点的vis先标记为一    dfs(1);    for(int i = 1; i <= n; ++i)    {        //cout << sum[i] << ' ';        if(sum[i]%2 == 0) ans++; // 节点个数为偶数则减    }    //cout << endl;    printf("%d\n", ans-1); //减一的理由是根节点节点数一定为偶数，但是其不能减。。}