İnəklərin yarışı (Həll təhlili)

$g$ Bulean matrisini elan edək. Hər $a$ və $b$ inək cütü üçün g[a][b] = true təyin edək, əgər $a$ inəyi $b$ inəyini məğlub edirsə. Beləliklə, $a$-dan $b$-yə istiqamətlənmiş kənar çəkək. Turların nəticələri ziddiyyətsiz olduğundan, qurulmuş qraf asiklikdir.

$i$ nömrəli inəyin rütbəsini o zaman müəyyən etmək olar ki, istənilən digər $j$ inəyi üçün onlardan hansının güclü olduğu məlum olsun: ya $i$ inəyi $j$ inəyini məğlub edə bilər (bəlkə də bir neçə aralıq inək vasitəsilə), ya da $j$ inəyi $i$ inəyini məğlub edə bilər. Başqa sözlə, qrafın tranzitiv qapanmasında hər $i$ və $j$ cütü üçün ən azı bir şərt yerinə yetirilməlidir: g[i][j] = true və ya g[j][i] = true.

Eyni zamanda həm g[i][j], həm də g[j][i] dəyərləri $true$ ola bilməz, çünki bu, yarışma nəticələrində ziddiyyət olduğunu göstərərdi.

Nümunə

Verilmiş nümunədə rütbələri yalnız $2$ və $5$ nömrəli inəklər üçün birmənalı şəkildə müəyyən etmək olar.

$2$ inəyi $5$ inəyini məğlub edir, lakin digər bütün inəklərə uduzur. $5$ inəyi digər bütün inəklərə uduzur.

$1$ nömrəli inək üçün onun $3$ və $4$ inəklərini məğlub edə biləcəyi məlum deyil. Analoji olaraq, $3$ və $4$ inəkləri üçün onların $1$ inəyini məğlub edə biləcəyi məlum deyil. Buna görə də bu inəklərin dəqiq rütbələrini müəyyən etmək mümkün deyil.

Alqoritmin tətbiqi

$g$ Bulean matrisini elan edək.

bool g[101][101];

Giriş məlumatlarını oxuyuruq.

scanf("%d %d", \u0026n, \u0026m);

Hər inəyin özünü məğlub etdiyini qəbul edirik.

for (i = 1; i \u003c= n; i++) g[i][i] = 1;

Giriş məlumatlarını oxuyuruq. Giriş qrafını qururuq. Əgər $a$ inəyi $b$ inəyini məğlub edibsə, $a$-dan $b$-yə kənar çəkirik.

for (i = 0; i \u003c m; i++)
{
  scanf("%d %d", \u0026a, \u0026b);
  g[a][b] = 1;
}

Qrafın tranzitiv qapanmasını hesablayırıq. Əgər $i$ təpəsindən $j$ təpəsinə qrafın kənarları boyunca yol mövcuddursa, g[i][j] = true təyin edirik.

for (k = 1; k \u003c= n; k++)
for (i = 1; i \u003c= n; i++)
for (j = 1; j \u003c= n; j++)
  if (g[i][k] \u0026\u0026 g[k][j]) g[i][j] = true;

$res$ dəyişənində rütbəsi birmənalı şəkildə müəyyən edilə bilən inəklərin sayını toplayırıq.

res = 0;

Dövrdə növbə ilə hər inəyi yoxlayır və onun rütbəsinin birmənalı şəkildə müəyyən edilib-edilmədiyini aydınlaşdırırıq.

for (i = 1; i \u003c= n; i++)
{

$i$ nömrəli inəyin rütbəsinin müəyyən edilib-edilmədiyini yoxlayaq. Bunun üçün bütün $j$ inəklərini sıra ilə nəzərdən keçirək. Əgər hər hansı bir inək üçün hər iki şərt yerinə yetirilirsə: g[i][j] = false və g[j][i] = false, onda bu iki inəkdən hansının güclü olduğunu müəyyən etmək mümkün deyil. Deməli, $i$ nömrəli inəyin dəqiq rütbəsini müəyyən etmək mümkün deyil.

  bool good = true;
  for (j = 1; j \u003c= n; j++)
    if (g[i][j] == false \u0026\u0026 g[j][i] == false)
    {
      good = false;
     break;
    }

Əgər bütün inəklərin yoxlanılmasından sonra $good$ dəyəri $true$ olaraq qalıbsa, deməli, $i$ inəyi üçün onun digər hər bir inəyə nisbətən vəziyyəti məlumdur. Deməli, onun rütbəsini birmənalı şəkildə müəyyən etmək olar.

  if (good) res++;
}

Cavabı çap edirik.

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