Tabe olanlar#11429

Tabe olanlar (Həll təhlili)

Şirkət strukturu bir ağacdır. Hər bir $v$ ağacının zirvəsi üçün onun kök olduğu alt ağacdaki zirvələrin sayını $s u m [v]$ tapmaq lazımdır. O zaman $v$ işçisinin altının sayını $s u m [v] - 1$ sum[v] - 1 (çünki işçi $v$ öz altı deyil) olaraq tapmaq olar.

Şirkətin baş direktoruna uyğun gələn 1-ci zirvədən danışıqları dərinlikdə ayaqlamağa başlayaq. Əgər $t o_{1}, t o_{2}, ..., t o_{k}$ to_1, to_2, ..., to_k $v$ zirvəsinin oğullarıdırsa, onda:

s u m [v] = 1 + s u m [t o_{1}] + s u m [t o_{2}] + ... + s u m [t o_{k}]

sum[v] = 1 + sum[to_1] + sum[to_2] + ... + sum[to_k]

Əgər $v$ zirvəsi ağacın yarpağıdırsa, onda $s u m [v] = 1$ sum[v] = 1 təyin edək.

Misal

Misalı nəzərdən keçirək. Hər bir işçinin (qraf zirvəsi) yanında onun altlarının sayı göstərilir.

Alqoritmin implementasiyası

Ağac qonşuluq siyahısında $g$ saxlanılır.

vector<vector<int> > g;

dfs funksiyası dinclikdə axtarışı zirvə $v$ -dən həyata keçirir və kökü $v$ olan alt ağacdakı zirvələrin sayını qaytarır. Zirvə $p$ , dinclikdə axtarışda $v$ -nin əcdadıdır.

int dfs(int v, int p)
{

Kökü $v$ olan alt ağac başlanğıcda yalnız bir zirvə - zirvə $v$ -ni ehtiva edir.

  sum[v] = 1;

$v \to t o$ v → to kənarını nəzərdən keçiririk. Əgər $t o \neq = p$ to \ne p, onda $s u m [v]$ -nin üzərinə kökü $t o$ olan alt ağacdakı zirvələrin sayını əlavə edirik.

  for (int to : g[v])
    if (to != p) sum[v] += dfs(to, v);

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

  return sum[v];
}

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq. Ağacı qururuq.

scanf("%d", &n);
g.resize(n + 1);

for (i = 2; i <= n; i++)
{
  scanf("%d", &x);

İşçi $i$ üçün şirkətdəki birbaşa müdir $x$ -dir.

  g[i].push_back(x);
  g[x].push_back(i);
}

1-ci zirvədən danışıqları dərinlikdə ayaqlamağa başlayaq.

sum.resize(n + 1);
dfs(1, -1);

Cavabı çıxardırıq. İşçi $i$ -nin altlarının sayı $s u m [i] -1$ -ə bərabərdir.

for (i = 1; i <= n; i++)
  printf("%d ", sum[i] - 1);
printf("\n");

Java implementasiyası


import java.util.*;

public class Main
{
  static ArrayList<Integer>[] g;	
  static int sum[];
  static int n;
  
  static int dfs(int v, int p)
  {
    sum[v] = 1;
    for(int to : g[v])
      if (to != p) sum[v] += dfs(to,v);
    return sum[v];
  }
  
  @SuppressWarnings("unchecked")
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    n = con.nextInt();
    g = new ArrayList[n+1]; // unchecked
    sum = new int[n+1];

    for (int i = 0; i <= n; i++)
      g[i] = new ArrayList<Integer>();

    for (int i = 2; i <= n; i++)
    {
      int x = con.nextInt();
      g[i].add(x);
      g[x].add(i);
    }
    
    dfs(1,-1);
    for (int i = 1; i <= n; i++)
      System.out.print(sum[i] - 1 + " ");    
    System.out.println();
    con.close();
  }
}

Java

Python implementasiyası

Rekursiya üçün steki artıracağıq.

import sys
sys.setrecursionlimit(1000000)

dfs funksiyası zirvə $v$ -dən dinclikdə axtarış həyata keçirir və kökü $v$ olan alt ağacdakı zirvələrin sayını qaytarır. Zirvə $p$ , dinclikdə axtarışda $v$ -nin əcdadıdır.

def dfs(v, p):

Kökü $v$ olan alt ağac başlanğıcda yalnız bir zirvə - zirvə $v$ -ni ehtiva edir.

  sum[v] = 1

$v \to t o$ v → to kənarını nəzərdən keçiririk. Əgər $t o \neq = p$ to \ne p, onda $s u m [v]$ -nin üzərinə kökü $t o$ olan alt ağacdakı zirvələrin sayını əlavə edirik.

  for to in g[v]:
    if to != p: sum[v] += dfs(to,v)

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

  return sum[v]

Proqramın əsas hissəsi. İşçilərin sayını $n$ oxuyuruq.

n = int(input())

Qrafagır orta siyahını $g$ inizialize edirik.

g = [[] for _ in range(n+1)]

Giriş məlumatlarını oxuyuruq. Ağacı qururuq.

lst = list(map(int, input().split()))
for i in range(2,n+1):
  a = lst[i-2]

İşçi $i (i \geq 2)$ i~(i \ge 2) üçün birbaşa müdir şirkətdə $a$ -dır.

  g[a].append(i)
  g[i].append(a)

$s u m$ siyahısını inizialize edirik.

sum = [0] * (n + 1)

1-ci zirvədən danışıqları dərinlikdə ayaqlamağa başlayaq.

dfs(1,-1)

Cavabı çıxardırıq. İşçi $i$ -nin altlarının sayı $s u m [i] - 1$ sum[i] - 1-ə bərabərdir.

for i in range(1, n+1):
  print(sum[i] - 1,end=" ")