Cüt ağac (Həll təhlili)

Məsələn, rabitə komponentlərinin sayını maksimuma çatdırmaq məqsədilə ağacı cüt sayıda zirvələrin olduğu komponentlərə parçalamaq lazımdır.

Ağacın kökü olan zirvə $1$-dən dərinlik üzrə axtarış edək. Hər bir zirvə $v$ üçün kökü $v$ olan alt ağacdakı zirvələrin sayını təyin edək. Bu say cütdürsə, dərinlik üzrə axtarışda $v$ zirvəsini onun atası ilə birləşdirən kənarı silək.

Kök üçün ($1$ zirvəsi) bütün ağacın ölçüsü cütdür. Lakin, $1$ zirvəsini atası ilə birləşdirən kənar mövcud deyil. Ona görə bu metodla əldə edilən nəticədən $1$ çıxmaq lazımdır.

Nümunə

Nümunədə göstərilən ağacı nəzərdən keçirək. Hər bir zirvənin yanında, əgər bu zirvəni kök hesab etsək, alt ağacın ölçüsü göstərilib. Zirvələr $1,3$ və $6$ cüt sayıda zirvəsi olan alt ağaclara malikdir. Çünki, zirvə $1$ kökdür və ataya getməyi təmin edən kənarı yoxdur, biz iki kənarı silirik: $(1,3)$ və $(1,6)$.

Ağac $3$ rabitəli komponentə ayrılıb və hər birində cüt sayıda zirvə var.

Alqoritmin reallaşdırılması

İşçi massivlər elan edək.

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

dfs funksiyası bir zirvədən $v$ dərinlik üzrə axtarış həyata keçirir və kökü $v$ olan alt ağacdakı zirvələrin sayını qaytarır.

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

$s$ dəyişənində kökü $v$ olan alt ağacdakı zirvələrin sayını hesablayırıq.

  int s = 1;

$v$ zirvəsinin övladlarını $i$ yoxlayırıq. $dfs(i)$ dəyərlərini $s$-ə əlavə edirik.

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

Əgər alt ağacın ölçüsü $s$ cütdürsə, $v$ ilə onun atası arasında olan kənarı silirik.

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

Kökü $v$ olan alt ağacdakı zirvələrin sayını qaytarırıq.

  return s;
}

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq. Qrafı qururuq.

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

Zirvə $1$-dən dərinlik üzrə axtarışı başlayırıq. $res$ dəyişəni daxilində silinmiş kənarların sayını sayırıq.

res = 0;
dfs(1);

$1$-dən onun atasına kənar yoxdur. res - 1-i çap edirik.

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

Python reallaşdırılması

dfs funksiyası $v$ zirvəsindən dərinlik üzrə axtarış həyata keçirir və kökü $v$ olan alt ağacdakı zirvələrin sayını qaytarır.

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

$s$ dəyişənində kökü $v$ olan alt ağacdakı zirvələrin sayını hesablayırıq.

  s = 1

$v$ zirvəsinin övladlarını $i$ yoxlayırıq. $dfs(i)$ dəyərlərini $s$-ə əlavə edirik.

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

Əgər alt ağacın ölçüsü $s$ cütdürsə, $v$ ilə onun atası arasında olan kənarı silirik.

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

Kökü $v$ olan alt ağacdakı zirvələrin sayını qaytarırıq.

  return s

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq. Qrafı qururuq.

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

Zirvə $1$-dən dərinlik üzrə axtarışı başlayırıq. $res$ dəyişəni daxilində silinmiş kənarların sayını sayırıq.

res = 0
dfs(1)

$1$-dən onun atasına kənar yoxdur. res - 1-i çap edirik.

print(res - 1)