Двоколірність#3165

Двоколірність (Розбір)

У задачі слід перевірити, чи можна розфарбувати граф у $2$ кольори так, щоб будь-які дві сусідні вершини мали різні кольори. Такий граф називається двочастковим.

Якщо здійснити пошук у глибину на графі, то:

Нехай перша вершина має колір $1$ ;
Тоді всі її сусіди повинні мати колір $2$ ;
Сусіди вершин з кольором $2$ повинні знову мати колір $1$ ;
І так далі...

Тобто кольори вершин повинні чергуватися за глибиною обходу.

Для розв'язання задачі скористаємось пошуком у глибину. Спочатку всі вершини вважаються невідвіданими і позначаються кольором $0$ . У процесі обходу графа будемо розфарбовувати вершини у два кольори: $1$ і $2$ . Якщо поточна вершина має колір $i$ (де $i = 1$ i = 1 або $2$ ), то кожну наступну вершину, в яку ми переходимо при обході в глибину, фарбуємо в колір $3 - i$ 3 - i. При цьому на кожному кроці перевіряємо, щоб жодні дві суміжні вершини не були пофарбовані в один і той же колір.

Приклад

Наведені в прикладі графи мають наступний вигляд:

Реалізація алгоритму

Матрицю суміжності графа будемо зберігати в масиві $g$ розміром $M A X = 1001$ MAX = 1001 (нумерація вершин ведеться від $1$ до $n \leq 1000$ n \le 1000). Масив $u se d$ зберігає інформацію про колір кожної вершини. Глобальна змінна $f l a g$ відповідає за коректність розфарбування: як тільки виявляються дві сусідні вершини, пофарбовані в один і той же колір, ця змінна приймає значення $1$ .

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

Функція dfs виконує пошук у глибину. Їй передаються два параметри: поточна вершина $v$ та її колір $co l or$ .

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

Якщо раніше вже було виявлено випадок, при якому необхідне розфарбування неможливе ( $f l a g = 1$ flag = 1), виконання функції припиняється.

  if (flag) return;

Позначаємо вершину $v$ кольором color.

  used[v] = color;

Переглядаємо всі вершини $i$ , в які можна перейти з вершини $v$ , продовжуючи обхід у глибину.

Якщо вершина $i$ ще не була відвідана, запускаємо з неї пошук у глибину, передаючи функції dfs протилежний колір.
Якщо вершина $i$ вже була відвідана, перевіряємо коректність розфарбування: якщо вершини $v$ і $i$ мають однаковий колір, це означає порушення умови двочастковості, і встановлюємо $f l a g = 1$ flag = 1.

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

Основний цикл програми. Читаємо кількість вершин $n$ та кількість ребер $l$ графа. Обнуляємо матрицю суміжності та масив $u se d$ .

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

Читаємо ребра графа.

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

Обнуляємо змінну $f l a g$ , і запускаємо пошук у глибину, починаючи з першої вершини, попередньо присвоївши їй колір $1$ .

   flag = 0; 
   dfs(1);

Залежно від значення змінної $f l a g$ виводимо результат.

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