Чи є цикл?#4004

Чи є цикл? (Розбір)

Запустим пошук в глибину на орієнтованому графі, розглядаючи його як несвязний. Для цього будемо використовувати масив $u se d$ , в якому зберігаються кольори вершин графа:

$u se d [v] = 0$ used[v] = 0 — вершина $v$ біла, ще не відвідана;
$u se d [v] = 1$ used[v] = 1 — вершина $v$ сірий, в неї вже увійшли, але обробка нащадків ще не завершена;
$u se d [v] = 2$ used[v] = 2 — вершина $v$ чорний, вона і всі її нащадки повністю оброблені.

Цикл в орієнтованому графі існує, якщо при пошуку в глибину виявлено ребро, що веде в сіру вершину.

Приклад

Приклади графів, наведені в умові задачі, мають наступний вигляд:

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

Оголосимо матрицю суміжності $g$ і масив станів вершин $u se d$ .

#define MAX 51
int g[MAX][MAX], used[MAX];

Функція dfs виконує обхід графа в глибину, починаючи з вершини $v$ .

void dfs(int v)
{

Позначаємо вершину $v$ як сіру, ми увійшли в неї.

  used[v] = 1;

Перебираємо всі вершини, в які можна потрапити з вершини $v$ .

  for (int i = 1; i <= n; i++)

З $v$ в $i$ існує ребро, якщо $g [v] [i] = 1$ g[v][i] = 1.

    if (g[v][i])
    {

Якщо вершина $i$ сіра, то в пошуку в глибину ми увійшли в сіру вершину — знайдено цикл.

      if (used[i] == 1) flag = 1;

Якщо вершина $i$ біла, то вона ще не відвідана. Продовжуємо пошук в глибину з неї.

      else if (used[i] == 0) dfs(i);

Якщо вершина $i$ чорна, то нічого не робимо.

Після завершення обробки всіх синів вершини $v$ , позначаємо її як чорною.

  used[v] = 2;
}

Основна частина програми. Читаємо матрицю суміжності.

scanf("%d", &n);
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
  scanf("%d", &g[i][j]);

Запускаємо пошук в глибину на орієнтованому графі (як на несвязному).

flag = 0;
for (i = 1; i <= n; i++)
  if (used[i] == 0) dfs(i);

Виводимо відповідь.

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

Java реалізація

import java.util.*;

public class Main
{
  static int g[][], used[];
  static int n, flag;
  static void dfs(int v)
  {
    // позначаємо вершину v як сіру, здійснюємо вхід в v
    used[v] = 1;

    // намагаємося піти з v в i, i = 1,2,...,n
    for (int i = 1; i <= n; i++)
      // якщо існує ребро з v в i
      if (g[v][i] == 1)
      {
         // якщо вершина i сіра, то зустрічаємо цикл
         if (used[i] == 1) flag = 1;
         // якщо вершина i не відвідана, запускаємо dfs звідти
         else if (used[i] == 0) dfs(i);
        // якщо вершина i чорна (used[i] = 2), нічого не робимо
      }
    // позначаємо вершину v як чорну, здійснюємо вихід з v
    used[v] = 2;
  }
  
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    n = con.nextInt();
    g = new int[n+1][n+1];
    used = new int[n+1];

    for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
      g[i][j] = con.nextInt();

    flag = 0;
    // запускаємо dfs на орієнтованому графі як на несвязному графі
    for (int i = 1; i <= n; i++)
      if (used[i] == 0) dfs(i);

    System.out.println(flag);    
  }
}

Java