CodeForces 964D Destruction of a Tree 【贪心】

发表于 | 更新于 | 分类于

题目大意：

给出一个由n个点和n - 1条边构成的树，每次可以摧毁掉一个度数为偶数的点，问是否存在一个摧毁的顺序使得所有点都能被摧毁掉。

解题思路：

先说结论：当n为偶数时，总会存在度数为奇数的点无法被摧毁掉(很明显的)。当n为奇数时，答案总是存在的(证明略)。
对于答案存在的情况，我们每次都摧毁靠近叶子结点的度数为偶数的结点，因为如果这个点不摧毁，而先摧毁了其父结点，那它的度数就变为奇数，并且叶子结点度数均为1，它们就无法消除了。

Mycode：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <stack>
#include <vector>
using namespace std;
const int MAX = 200010;

bool vis[MAX];
stack<int> sta;
vector<int> G[MAX], res;
int n, t, tem, deg[MAX], f[MAX];
void DFS(int x, int p)
{
    sta.push(x);
    f[x] = p;
    for(int i = 0; i < G[x].size(); ++i)
    {
        if(G[x][i] == p)    continue;
        DFS(G[x][i], x);
    }
}
void DFS2(int x)
{
    res.push_back(x);
    vis[x] = true;
    for(int i = 0; i < G[x].size(); ++i)
    {
        int nex = G[x][i];
        --deg[nex];
        if(nex == f[x]) continue;
        if(vis[nex])    continue;
        if(deg[nex] % 2 == 0)
            DFS2(nex);
    }
}
int main()
{
    scanf("%d", &n);
    if(n & 1)
    {
        puts("YES");
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d", &t);
            if(!t)
                continue;
            ++deg[t], ++deg[i];
            G[t].push_back(i);
            G[i].push_back(t);
        }
        DFS(1, 0);
        while(!sta.empty())
        {
            tem = sta.top();
            sta.pop();
            if(deg[tem] % 2 == 0)
                DFS2(tem);
        }
        for(int i = 0; i < res.size(); ++i)
            printf("%d\n", res[i]);
    }
    else
        puts("NO");
    return 0;
}
Donate comment here
0%