Парне дерево (Розбір)

У задачі потрібно виконати декомпозицію дерева на компоненти зв'язності з парним числом вершин. При цьому слід максимізувати кількість цих компонент.

Запустимо пошук у глибину з вершини $1$, яка є коренем дерева. Для кожної вершини $v$ визначимо кількість вершин у піддереві з коренем $v$. Якщо це число парне, то видалимо ребро, що з'єднує $v$ з його батьком при пошуку в глибину.

Для кореня (вершини $1$) розмір всього дерева парний. Проте ребра, що з'єднує вершину $1$ з її батьком, не існує. Тому з результату, отриманого за вищенаведеним алгоритмом, слід відняти $1$.

Приклад

Розглянемо дерево, наведене в прикладі. Поруч із кожною вершиною зазначено розмір піддерева, якщо розглядати цю вершину як корінь. Вершини $1,3$ і $6$ мають піддерева з парним числом вершин. Оскільки вершина $1$ є коренем і не має ребра, що веде до батька, ми видаляємо два ребра: $(1,3)$ і $(1,6)$.

Дерево розпалось на $3$ компоненти зв'язності, кожна з яких містить парне число вершин.

Реалізація алгоритму

Оголосимо робочі масиви.

#define MAX 101
int g[MAX][MAX], used[MAX];

Функція dfs виконує пошук у глибину з вершини $v$ і повертає кількість вершин у піддереві з коренем $v$.

int dfs(int v)
{
  used[v] = 1;

У змінній $s$ обчислюємо кількість вершин у піддереві з коренем $v$.

  int s = 1;

Перебираємо синів $i$ вершини $v$. Додаємо до $s$ значення $dfs(i)$.

  for (int i = 1; i <= n; i++)
    if (g[v][i] && !used[i]) s += dfs(i);

Якщо розмір піддерева $s$ парний, видаляємо ребро між $v$ і його батьком.

  if (s % 2 == 0) res++;

Повертаємо кількість вершин у піддереві з коренем $v$.

  return s;
}

Основна частина програми. Читаємо вхідні дані. Будуємо граф.

scanf("%d %d", &n, &m);
for (i = 0; i < m; i++)
{
  scanf("%d %d", &a, &b);
  g[a][b] = g[b][a] = 1;
}

Запускаємо пошук у глибину з вершини $1$. У змінній $res$ підраховуємо кількість видалених ребер.

res = 0;
dfs(1);

Ребра з $1$ до її батька не існує. Виводимо res - 1.

printf("%d\n", res - 1);

Python реалізація

Функція dfs виконує пошук у глибину з вершини $v$ і повертає кількість вершин у піддереві з коренем $v$.

def dfs(v):
  used[v] = 1

У змінній $s$ обчислюємо кількість вершин у піддереві з коренем $v$.

  s = 1

Перебираємо синів $i$ вершини $v$. Додаємо до $s$ значення $dfs(i)$.

  for i in range(1, n + 1):
    if g[v][i] and not used[i]:
      s += dfs(i)

Якщо розмір піддерева $s$ парний, видаляємо ребро між $v$ і його батьком.

  if s % 2 == 0:
    global res
    res += 1

Повертаємо кількість вершин у піддереві з коренем $v$.

  return s

Основна частина програми. Читаємо вхідні дані. Будуємо граф.

n, m = map(int, input().split())
g = [[0] * (n + 1) for _ in range(n + 1)]
used = [0] * (n + 1)

for _ in range(m):
  a, b = map(int, input().split())
  g[a][b] = g[b][a] = 1

Запускаємо пошук у глибину з вершини $1$. У змінній $res$ підраховуємо кількість видалених ребер.

res = 0
dfs(1)

Ребра з $1$ до її батька не існує. Виводимо res - 1.

print(res - 1)