Dövrü axtarış (Həll təhlili)

Qrafın dərinlik üzrə keçidini təşkil edərək seriyanı yerinə yetirək. Bunun üçün hələ keçilməmiş hər bir zirvədən dərinlik üzrə axtarış başladaq. Zirvəyə daxil olarkən onu boz rəngə boyayacağıq, çıxarkən isə — qara rəngə. Əgər axtarış zamanı artıq boz rəngə boyanmış zirvəyə keçməyə cəhd edəriksə, bu bir dövrə tapıldığı anlamına gələcək.

Dövrəni bərpa etmək üçün zirvələri keçid qaydasında yadda saxlamaq lazımdır. Məsələn, əgər keçid kütləsi (2, 6, 3, 5, 4, 3) zirvələrini ehtiva edirsə, axtarılan dövrə (3, 5, 4) olacaq.

Misal

Məsələnin şərtində təqdim olunan qraflar aşağıdakı formadadır:

Hər bir zirvənin yanındakı dəyər cari $path$ massivinin vəziyyətini göstərir.

Alqoritmin reallaşdırılması

Qrafın qonşuluq siyahısı $g$ vektorunda saxlanılır. $path$ massivində dərinlik üzrə keçid qaydasında zirvələrin ardıcıllığını saxlayırıq.

vector<vector<int> > g;
vector<int> used, path;

dfs funksiyası $v$ zirvəsindən dərinlik üzrə axtarış aparır. $v$ zirvəsinə daxil olarkən onu boz rəngdə boyayırıq (used[v] = 1), çıxarkən isə — qara rəngdə (used[v] = 2). Global $flag$ dəyişəni dövrənin olub-olmamasını göstərir: flag = 1 dövrənin tapıldığını, flag = 0 isə dövrənin olmadığını müəyyən edir.

void dfs(int v)
{

Əgər dövrə artıq tapılmışdırsa (flag = 1), axtarışa davam etməyin mənası yoxdur.

  if (flag == 1) return;

$v$ zirvəsini boz rəngdə qeyd edir və $path$ massivinə əlavə edirik.

  used[v] = 1; 
  path.push_back(v);

$v$ ilə qonşu olan $to$ zirvələrini nəzərdən keçiririk.

  for (int to : g[v])

Dövrə tapılmış hesab olunur, əgər dərinlik üzrə axtarış boz zirvəyə keçməyə çalışırsa (yəni $to$ zirvəsi üçün used[to] = 1)).

    if (used[to] == 1) 
    {
      path.push_back(to);
      flag = 1;
      return;
    }

Əgər $to$ zirvəsi hələ ağdırsa, onda ondan dərinlik üzrə axtarışa davam edirik.

    else 
    {
      if (used[to] == 0) dfs(to);
      if (flag == 1) return;
    }

$v$ zirvəsinin işlənməsi başa çatdıqdan sonra onu qara rəngdə qeyd edirik. $path$ massivindən $v$ zirvəsini silirik.

  used[v] = 2;
  path.pop_back();
}

Proqramın əsas hissəsi. Kənarların siyahısını oxuyur və qrafın qonşuluq siyahısını qurur.

scanf("%d %d", &n, &m);
g.resize(n + 1); used.resize(n + 1, 0);
for(i = 0; i < m; i++)
{
  scanf("%d %d",&a,&b);
  g[a].push_back(b);
}

Dərinlik üzrə keçidlər silsiləsini işə salırıq. Əgər $i$ zirvəsi hələ işlənməyibsə (used[i] = 0), onda ondan dərinlik üzrə axtarışa başlayırıq. Əgər növbəti dfs funksiyası çağırışının icrası zamanı $flag$ dəyiəni $1$ olursa (qrafda dövrə aşkarlanıb), onda axtarışı dayandırırıq.

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

Əgər flag = 1, bu o deməkdir ki, dövrə tapıldı. Belə olan halda, $path$ massivindəki məlumata əsasən onu çıxarırıq.

if (flag == 1)
{

Dövrə tapılıb və o, cfin = path[path.size() - 1] zirvəsində başa çatır.

  cfin = path.back();

$cstart$ dəyişəni ilə $path$ massivində geri hərəkət edirik ki, elə həmin $cfin$ zirvəsini tapaq — dövrənin başladığı nöqtəni.

  cstart = path.size() - 2;
  while (path[cstart] != cfin) cstart--;

Dövrənin mövcudluğu və dövrənin özü barədə məlumat çıxarırıq.

  printf("YES\n");
  for (i = cstart; i < path.size() - 1; i++)
    printf("%d ", path[i]);
  printf("\n");
}

Əks halda (flag = 0) qrafda dövrə yoxdur.

else printf("NO\n");

Java reallaşdırılması

import java.util.*;

public class Main
{
  static ArrayList<Integer>[] g;
  static int used[], flag, n, m;
  static Vector<Integer> path = new Vector<Integer>();

  static void dfs(int v)
  {
    if (flag == 1) return;
    used[v] = 1; 
    path.add(v);

    for (int i = 0; i < g[v].size(); i++)
    {
      int to = g[v].get(i);
      if (used[to] == 1)
      {
        path.add(to);
        flag = 1;
        return;
      }
      else dfs(to);
      if (flag == 1) return;
    }
	  
    used[v] = 2;
    path.remove(path.size() - 1);
  }

  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    n = con.nextInt();
    m = con.nextInt();

    g = new ArrayList[n+1];
    for (int i = 0; i <= n; i++)
      g[i] = new ArrayList<Integer>();    
    used = new int[n+1];
    
    for(int i = 0; i < m; i++)
    {
      int a = con.nextInt();
      int b = con.nextInt();
      g[a].add(b);      
    }
    
    for (int i = 1; i <= n; i++)
      if (used[i] == 0)
      {
        dfs(i);
        if (flag == 1) break;
      }
 
    if (flag == 1)
    {
      int i = path.size() - 2;
      int to = path.lastElement();
      while (path.get(i) != to) i--;

      System.out.println("YES");
      for (; i < path.size() - 1; i++)
        System.out.print(path.get(i) + " ");
      System.out.println();
    }
    else System.out.println("NO");
    con.close();
  }
}