算法知识点: 搜索

复杂度：

解题思路：

由于这道题目的数据较弱，且贪心算法均有反例，因此直接暴搜出所有切割方案，保留最小值即可。

首先预处理出每一层的节点集合，以及每棵子树的大小。

然后从第一层开始，依次枚举每一层中删除哪棵子树，枚举之后通过深度优先遍历，将整棵子树中的边全部标记为不可选，再递归到下一层继续枚举。递归结束时需要再次深度优先遍历整棵子树，将每条边的状态恢复为可选。

当枚举到最后一层时，更新最小值。

暴力枚举过程中需要维护当前已经删除的节点总数。

C++ 代码： 

#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std; const int N = 310,
    M = 610;
 
int n, m;
int h[N], e[M], ne[M], c[M], idx;
int size[N];
vector<int> level[N];
 
int ans = N, max_depth;
 
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
 
int dfs_level(int u, int depth, int father)
{
    size[u] = 1;
    max_depth = max(max_depth, depth);
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j != father)
        {
            level[depth].push_back(i);
            size[u] += dfs_level(j, depth + 1, u);
        }
    }
    return size[u];
}
 
void dfs_draw(int i, bool color)
{
    c[i] = color;
    for (int j = h[e[i]]; j != -1; j = ne[j])
        if (j != (i ^ 1))
            dfs_draw(j, color);
}
 
void dfs(int u, int s)
{
    ans = min(ans, n - s);
 
    if (u == max_depth) return;
 
    for (auto i: level[u])
        if (!c[i])
        {
            dfs_draw(i, true);
            dfs(u + 1, s + size[e[i]]);
            dfs_draw(i, false);
        }
}
 
int main()
{
    memset(h, -1, sizeof h);
 
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }
 
    dfs_level(1, 0, -1);
 
    dfs(0, 0);
 
    cout << ans << endl;
 
    return 0;
}


另外，牛客暑期NOIP真题班限时免费报名
报名链接：https://www.nowcoder.com/courses/cover/live/248
报名优惠券：DCYxdCJ