Unikal rəng#10654

Unikal rəng (Həll təhlili)

Təpə $1$ -dən dərinliyə doğru axtarış başladırıq. Təpə $v$ -yə daxil olarkən $co l or [v]$ color[v] rəngini alırıq və $u se d [co l or [v]]$ used[color[v]] dəyərini $1$ artırırıq. $u se d [co l or [v]]$ used[color[v]] dəyəri, $1$ təpəsindən $v$ təpəsinə qədər (daxil olmaqla) yol boyunca $co l or [v]$ color[v] rənginin neçə dəfə təkrarladığını bildirir. Əgər bu rəng bu yolda yalnız bir dəfə təkrarlanırsa, o zaman $v$ təpəsi yaxşıdır və biz onu nəticə dəstinə əlavə edirik.

Təpə $v$ -dən çıxərkən $u se d [co l or [v]]$ used[color[v]] dəyərini $1$ azaldırıq.

Misal

Birinci misaldakı qraf bu cür görünür:

Təpə $5$ yaxşı deyil, çünki $1 - 2 - 5$ 1 - 2 - 5 yolunda təpələr $5$ və $1$ eyni rəngdədir.

Təpə $6$ yaxşıdır, çünki $1 - 2 - 3 - 6$ 1 - 2 - 3 - 6 yolunda aralıq təpələrin rəngləri $6$ təpəsinin rəngindən fərqlidir.

Alqoritmanın tətbiqi

Daxil olan qrafı $g$ qonşuluq siyahısında saxlayırıq. İşlədici massivlər elan edirik.

vector<int> used, color;
vector<vector<int>> g;
set<int> st;

dfs funksiyası dərinliyə doğru axtarışı həyata keçirir. $p a r$ dəyişəni $v$ təpəsinin əcdadıdır.

void dfs(int v, int par)
{

Təpə $v$ rəngi $co l or [v]$ color[v]-dir. $1$ təpəsindən bu rəngdə təpənin qarşılandığını qeyd edirik.

  used[color[v]]++;

$u se d [co l or [v]]$ used[color[v]] dəyəri, $1$ təpəsindən $v$ təpəsinə qədər yolda (daxil olmaqla) $co l or [v]$ color[v] rənginin neçə dəfə qarşılandığını göstərir. Əgər bu rəng yolda yalnız bir dəfə qarşılanırsa, $v$ təpəsi yaxşı hesab olunur və onu nəticə dəsti $s t$ -ə əlavə edirik.

  if (used[color[v]] == 1) st.insert(v);

Təpə $v$ -dən çıxan bütün qövs $(v, t o)$ (v, to)-ları gözdən keçirik. Əgər to təpəsi $v$ -nin əcdadı deyil $(t o \neq = p a r)$ (to \ne par), ondan dərinliyə doğru axtarış başladırıq. Bu zaman $t o$ təpəsinin əcdadı $v$ olur.

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

Təpə $v$ -dən çıxanda $u se d [co l or [v]]$ used[color[v]] dəyərini $1$ azaldırıq.

  used[color[v]]--;
}

Proqramın əsas hissəsi. Təpələrin sayı $n$ və rəng massivi oxunur.

scanf("%d", &n);
color.resize(n + 1);
for (i = 1; i <= n; i++)
  scanf("%d", &color[i]);

Qraf oxunur.

used.resize(100001);
g.resize(n + 1);
for (i = 1; i < n; i++)
{
  scanf("%d %d", &x, &y);
  g[x].push_back(y);
  g[y].push_back(x);
}

C++

Təpə $1$ -dən dərinliyə doğru axtarış başlayırıq.

dfs(1, 1);

Yaxşı təpələr çıxış edilir. Onlar $s t$ dəstində saxlanır.

for (int val : st)
  printf("%d\n", val);