Avtomobil yarışları (Həll təhlili)

Problemdə bağlantılı yönsüz qraf verilmişdir. İstənilir ki, bunun bir dövrə (Formula-0 yoluna çevrilə biləcək) ehtiva edib-etmədiyini yoxlamaqdır.

Yönsüz bir qrafda dövrə mövcuddur, əgər geri dönən bir kənar varsa. Yəni, artıq keçilmiş bir zirvəyə gedən kənar varsa.

Misal

Misaldakı qrafların şəkli belədir:

Birinci qraf dövrə ehtiva edir, ikincisi isə etməz.

Alqoritmin təsviri

Qrafı qonşuluq matrisi $g$ ilə saxlayırıq. visited adlı array-i isə keçilmiş zirvələri işarələmək üçün istifadə edirik.

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

dfs funksiyası zirvə $v$-dən dərinlik üzrə axtarışı həyata keçirir. Və uca bir zirvədən $v$-ə yönəldiyimiz vəziyyətdə (atmış, dövrə olmadığı halda) halı kəsib atmamız lazımdır. Bunun üçün dfs funksiyasında ikinci parametr $p$ — zirvə $v$-nin atası parametrini daxil edəcəyik.

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

Zirvə $v$ işarələnmiş kimi qəbul edilir.

  used[v] = 1;

$V$ zirvəsindən keçilə biləcək zirvələri $i$ ilə keçiririk.

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

Ataya yönələn kənar xaric belə situasiya yoxlanır.

    if (i == p) continue;

$V$-dən $i$-yə, $i$-nin artıq keçilmiş olduğu bir kənarın var olduğu hallar üçün (yəni, used[i] = 1), qrafda bir dövrə mövcuddur. flag = 1 olaraq təyin edilir.

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

Əks halda, $i$ zirvəsindən dərinlik üzrə axtarışı davam edirik.

      else dfs(i, v);
    }
  }
}

Proqramın əsas hissəciyi. Giriş məlumatlarını oxuyuruq.

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

Girişdəki yönsüz qrafı oxuyuruq. Qrafı qonşuluq matrisi olaraq saxladığımızdan təkrarlanan yollar yalnız bir dəfə nəzərə alınacaqdır.

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

Əvvəlcə qrafda dövrənin mövcud olmadığını göstərən flag = 0 olaraq təyin edirik. Dövrə tapılsa, flag dəyişəni 1 olacaq.

flag = 0;

Zirvə 1-dən (tapşırıqda qrafın bağlantı olduğunu nəzərə alaraq) dərinlik üzrə axtarışı başlatırıq.

dfs(1);

Flag dəyişəninə görə cavabı çıxardırıq.

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

Java tətbiqi

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 tətbiqi

dfs funksiyası zirvə $v$-dən dərinlik üzrə axtarışı həyata keçirir. Və uca bir zirvədən $v$-ə yönəldiyimiz vəziyyətdə (atmış, dövrə olmadığı halda) halı kəsib atmamız lazımdır. Bunun üçün dfs funksiyasında ikinci parametr $p$ — zirvə $v$-nin atası parametrini daxil edəcəyik.

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

Zirvə $v$ keçilmiş kimi işarələnir.

  used[v] = 1

$V$ zirvəsindən keçilə biləcək zirvələri $i$ ilə keçiririk.

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

Ataya yönələn kənar xaric belə situasiya yoxlanır.

    if i == p:
      continue

$V$-dən $i$-yə, $i$-nin artıq keçilmiş olduğu bir kənarın var olduğu hallar üçün (yəni, used[i] = 1), qrafda bir dövrə mövcuddur. flag = 1 olaraq təyin edilir.

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

Əks halda, $i$ zirvəsindən dərinlik üzrə axtarışı davam edirik.

      else:
        dfs(i, v)

Proqramın əsas hissəciyi. Giriş məlumatlarını oxuyuruq.

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

Girişdəki yönsüz qrafı oxuyuruq. Qrafı qonşuluq matrisi olaraq saxladığımızdan təkrarlanan yollar yalnız bir dəfə nəzərə alınacaqdır.

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

Əvvəlcə qrafda dövrənin mövcud olmadığını göstərən flag = 0 olaraq təyin edirik. Dövrə tapılsa, flag dəyişəni 1 olacaq.

flag = 0

Zirvə 1-dən (tapşırıqda qrafın bağlantı olduğunu nəzərə alaraq) dərinlik üzrə axtarışı başlatırıq.

dfs(1)

Flag dəyişəninə görə cavabı çıxardırıq.

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