algorithm - hackerrank偶数树解法讲解(偶数节点的森林)

Question

我在 hackerrank 上做这个名为 Even Tree 的问题:

https://www.hackerrank.com/challenges/even-tree

一开始我不知道如何切割边缘并从树中 build 森林。所以我在网上查了一下，在 stackeverflow 上看到了这个答案:

Obtain forest out of tree with even number of nodes

好吧，只计算 child 的数量看起来简单多了，我用 C++ 实现了它:

#include <iostream>
#include <list>
#include <vector>
using namespace std;

int main() {
  int N, M, ans = 0;
  cin >> N >> M;
  vector<int> tree(N+1);
  vector<int> count(N+1);

  fill(count.begin(), count.end(), 1);
  for(int i = 0; i < M; i++) {
    int p, q;
    cin >> p >> q;
    tree[p] = q;

    int root = tree[p];

    // updating ancesors child count
    while(root) {
      count[root] += count[p];
      root = tree[root];
    }
  }

  int counter = 0;
  // displaying results
  for(int i = 2; i < count.size(); i++) {
    cout << count[i] << " ";
    if(count[i]%2 == 0)
      counter++;
  }
  cout <<"\nans : " <<  counter << endl;
  return 0;
}

我的问题是:这种方法如何运作？有多少 child 与选择边数最少的树有关？我不只是想复制解决方案，我想了解其背后的实际逻辑。请帮忙

Answer 1

首先，问题说所有测试用例(所有输入树)，存在一种删除边缘的方法，以便保留森林的均匀大小。当然，由于结果森林中的每棵树的大小都是偶数，这意味着节点总数 N 必须是偶数。偶数树必须有解，因为它们至少可以移除 0 条边以形成偶数森林。

注意有一些边不能被移除，即连接叶节点的边。于是我脑子里冒出一些贪心的想法，结果证明我可以证明它们，所以它们成为可以解决问题的贪心算法。

---

我声称

a) 任何偶数大小的子树，我们可以安全地从原始图中删除它们以减少问题而不影响结果，方法是删除子树根及其父节点的边(如果存在) )

b) 任何奇数大小的子树，我们可以用单个节点替换整个子树以减少问题。子树根的边及其父不能被删除(如果存在)

我们用反证法证明a)。假设如果我们删除图的偶数子树将使问题从可解变为不可解。考虑去掉偶数子树后的图，如果是奇数，则原图也无解；如果它的大小是偶数，那么它必须在删除偶数子树后有解决方案。这两种情况都会产生矛盾。

b) 非常简单，因为子树是奇数大小，其奇偶校验与单个叶节点相同，必须与其父节点连接。所以我们可以用单个节点替换子树来减少问题。

---

通过a)和b)，我们可以从树的叶子做贪心算法(因为我们已经知道必须选择连接叶子的边，他们正在形成子树，我们可以从这里开始减少问题)

1. 将所有叶子与他们的 parent 联系起来
2. 对所有形成的子树，如果子树是偶数，则全局答案计数器加1，移除子树；如果子树是奇数，则将其替换为单个节点(现在也是叶子节点)。
3. 重复2直到最多剩下1个节点

---

就是这样。从概念上讲，这就是算法。

虽然您可以使用许多不同的方法来实现它，但我使用 DFS，它非常直接地将此算法转换为代码。

一些简单地计算子树的数量，因为这可以判断子树是奇数还是偶数。

有人甚至只计算偶数度的节点数! (这是迄今为止我所知道的最聪明的解决方案)

但它们背后都有相同的概念:判断子树是否为奇数大小或偶数大小，删除它们(并增加答案计数器)或用单个节点替换它们以减少问题。

所有实现也具有相同的复杂度 O(N)。

这是我接受的代码:

#include<bits/stdc++.h>
using namespace std;

int w[105][105] = {0}, v[105] = {0};
int n,m,ans=0;

int dfs(int x){
    v[x] = 1;
    int son = 0;
    for(int i=0; i<105;i++) 
        if(w[x][i] && !v[i]) son += dfs(i);
    if(son % 2) { ans++; return 0;}
    return 1;
}

int main() {
    scanf("%d%d", &n,&m);
    for(int i=0,a,b; i<m;i++){
        scanf("%d%d", &a,&b);
        w[a][b] = w[b][a] = 1;
    }
    dfs(1);
    printf("%d\n", ans-1);  
    return 0;
}