Автогонки (Розбір)

У задачі задано неорієнтований зв'язний граф. Необхідно перевірити, чи містить він цикл (який можна перетворити в трасу Формули-0).

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

Приклад

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

Перший граф містить цикл, другий ні.

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

Граф зберігаємо у матриці суміжності $g$. Масив used використовуємо для позначення пройдених вершин.

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

Функція dfs реалізує пошук в глибину з вершини $v$. Необхідно відсікати випадок, коли з $v$ ми спрямовуємось до предка: предок вже пройдений, але циклу немає. Для цього у функції dfs введемо другий параметр $p$ — предка вершини $v$.

void dfs(int v, int p = -1)
{

Позначаємо вершину $v$ пройденою.

  used[v] = 1;

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

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

Розглядаємо всі ребра, крім того, яке веде до предка $p$.

    if (i == p) continue;

Якщо є ребро з $v$ у $i$, причому $i$ вже пройдена (used[i] = 1), то в графі є цикл. Встановлюємо flag = 1.

    if (g[v][i] == 1)
    {
      if (used[i] == 1) flag = 1;

Інакше продовжуємо пошук в глибину з вершини $i$.

      else dfs(i, v);
    }
  }
}

Основна частина програми. Читаємо вхідні дані.

scanf("%d %d",&n,&m);
memset(g,0,sizeof(g));
memset(used,0,sizeof(used));

Читаємо вхідний неорієнтований граф. Граф зберігаємо в матриці суміжності, тому повторювані дороги будуть враховуватись тільки один раз.

for (i = 0; i < m; i++)
{
  scanf("%d %d",&u,&v);  
  g[u][v] = g[v][u] = 1;
}

Встановимо flag = 0, що означає відсутність циклу в графі. Якщо цикл буде знайдено, значення змінної $flag$ зміниться на $1$.

flag = 0;

Запускаємо пошук в глибину з вершини $1$ (за умовою задачі граф зв'язний).

dfs(1);

Залежно від значення змінної $flag$ виводимо відповідь.

if (flag) printf("YES\n");
else printf("NO\n");

Java реалізація

import java.util.*;

public class Main
{
  static int g[][], used[];
  static int n, m, flag;

  static void dfs(int v, int prev)
  {
    used[v] = 1;
    for(int i = 1; i <= n; i++)
      if ((i != prev) && g[v][i] == 1)
        if (used[i] == 1) flag = 1; else dfs(i,v);
  }
  
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    n = con.nextInt();
    m = con.nextInt();    
    g = new int[n+1][n+1];
    used = new int[n+1];

    for(int i = 0; i < m; i++)
    {
      int u = con.nextInt();
      int v = con.nextInt();
      g[u][v] = g[v][u] = 1; 
    }
    
    flag == 0;
    dfs(1,-1);

    if (flag == 1) System.out.println("YES");
    else System.out.println("NO");
  }
}   

Python реалізація

Функція dfs реалізує пошук в глибину з вершини $v$. Необхідно відсікати випадок, коли з $v$ ми спрямовуємось до предка: предок вже пройдений, але циклу немає. Для цього у функції dfs введемо другий параметр $p$ — предка вершини $v$.

def dfs(v, p = -1):
  global flag

Позначаємо вершину $v$ пройденою.

  used[v] = 1

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

  for i in range(1, n + 1):

Розглядаємо всі ребра, крім того, яке веде до предка $p$.

    if i == p:
      continue

Якщо є ребро з $v$ у $i$, причому $i$ вже пройдена (used[i] = 1), то в графі є цикл. Встановлюємо flag = 1.

    if g[v][i] == 1:
      if used[i] == 1:
        flag = 1

Інакше продовжуємо пошук в глибину з вершини $i$.

      else:
        dfs(i, v)

Основна частина програми. Читаємо вхідні дані.

n, m = map(int, input().split())
g = [[0] * (n + 1) for _ in range(n + 1)]
used = [0] * (n + 1)

Читаємо вхідний неорієнтований граф. Граф зберігаємо в матриці суміжності, тому повторювані дороги будуть враховуватись тільки один раз.

for _ in range(m):
  a, b = map(int, input().split())
  g[a][b] = g[b][a] = 1

Встановимо flag = 0, що означає відсутність циклу в графі. Якщо цикл буде знайдено, значення змінної $flag$ зміниться на $1$.

flag = 0

Запускаємо пошук в глибину з вершини $1$ (за умовою задачі граф зв'язний).

dfs(1)

Залежно від значення змінної $flag$ виводимо відповідь.

if flag == 1:
  print("YES")
else:
  print("NO")