İki rəngli olma (Həll təhlili)

Məsələdə qrafı elə $2$ rəngə boyamağın mümkün olub-olmadığını yoxlamaq lazımdır ki, hər hansı iki qonşu təpə fərqli rəngdə olsun. Belə qraf ikitərəfli (двудольный) adlanır.

Əgər qraf üzərində dərinliyinə axtarış həyata keçirsək, onda:

• Tutaq ki, birinci təpənin rəngi $1$-dir;

• Onda onun bütün qonşuları $2$ rənginə malik olmalıdır;

• $2$ rəngli təpələrin qonşuları yenidən $1$ rəngində olmalıdır;

• Və beləliklə davam edir...

Yəni təpələrin rəngləri gəzintinin dərinliyi üzrə növbələşməlidir.

Məsələnin həlli üçün dərinliyinə axtarışdan istifadə edəcəyik. Əvvəlcə bütün təpələr ziyarət edilməmiş sayılır və $0$ rəngi ilə işarələnir. Qrafı gəzərkən təpələri iki rəngə: $1$ və $2$-yə boyayacağıq. Əgər cari təpənin rəngi $i$-dirsə (burada i = 1 və ya $2$), onda dərinliyinə gəzinti zamanı keçdiyimiz hər növbəti təpəni 3 - i rənginə boyayırıq. Bu zaman hər addımda yoxlayırıq ki, heç bir iki qonşu təpə eyni rəngə boyanmasın.

Misal

Misalda verilmiş qraflar aşağıdakı görünüşə malikdir:

Alqoritmin realizasiyası

Qrafın qonşuluq matrisini MAX = 1001 ölçülü $g$ massivində saxlayacağıq (təpələrin nömrələnməsi $1$-dən n \le 1000-ə qədər aparılır). $used$ massivi hər təpənin rəngi haqqında məlumatı saxlayır. $flag$ qlobal dəyişəni boyamanın düzgünlüyünə cavabdehdir: eyni rəngə boyanmış iki qonşu təpə aşkar edildiyi anda bu dəyişən $1$ qiymətini alır.

#define MAX 1000
int g[MAX][MAX], used[MAX], flag;

dfs funksiyası dərinliyinə axtarışı yerinə yetirir. Ona iki parametr ötürülür: cari təpə $v$ və onun rəngi $color$.

void dfs(int v, int color = 1)
{

Əgər əvvəllər artıq tələb olunan boyamanın mümkün olmadığı hal aşkar edilibsə (flag = 1), funksiyanın icrası dayandırılır.

  if (flag) return;

$v$ təpəsini color rənginə boyayırıq.

  used[v] = color;

$v$ təpəsindən keçə biləcəyimiz bütün $i$ təpələrinə baxırıq, dərinliyinə gəzintini davam etdirərək.

• Əgər $i$ təpəsi hələ ziyarət edilməyibsə, ondan başlayaraq dərinliyinə axtarışı işə salırıq, dfs funksiyasına əks rəngi ötürərək.

• Əgər $i$ təpəsi artıq ziyarət edilibsə, boyamanın düzgünlüyünü yoxlayırıq: əgər $v$ və $i$ təpələri eyni rəngə malikdirsə, bu ikitərəflilik şərtinin pozulması deməkdir, və flag = 1 təyin edirik.

  for (int i = 1; i \le= n; i++)
    if (g[v][i] == 1)
      if (used[i] == 0) dfs(i, 3 - color); else
      if (used[v] == used[i]) flag = 1;
}

Proqramın əsas dövrü. Qrafın təpələrinin sayı $n$ və tillərinin sayı $l$-i oxuyuruq. Qonşuluq matrisini və $used$ massivini sıfırlayırıq.

while(scanf("%d %d",&n,&l), n)
{
   memset(g,0,sizeof(g));
   memset(used,0,sizeof(used));

Qrafın tillərini oxuyuruq.

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

$flag$ dəyişənini sıfırlayırıq və dərinliyinə axtarışı birinci təpədən başlayaraq işə salırıq, əvvəlcədən ona $1$ rəngini mənimsətdikdən sonra.

   flag = 0; 
   dfs(1);

$flag$ dəyişəninin qiymətindən asılı olaraq nəticəni çap edirik.

   if (flag) printf("NOT BICOLOURABLE.\n");
   else printf("BICOLOURABLE.\n");
}