Dairə varmı?#4004

Dairə varmı? (Həll təhlili)

Yonlü qrafda təkrar dərinlik üzrə axtarış yerinə yetirəcəyik, onu əlaqəli olmayan kimi nəzərdən keçirəcəyik. Bunun üçün qrafın zirvələrinin rənglərini saxlayan $u se d$ massivindən istifadə edəcəyik:

$u se d [v] = 0$ used[v] = 0 — $v$ zirvəsi ağdır, hələ ziyarət edilməyib;
$u se d [v] = 1$ used[v] = 1 — $v$ zirvəsi boz rəngdədir, ona artıq daxil olunub, lakin nəsillərin işlənməsi hələ başa çatmayıb;
$u se d [v] = 2$ used[v] = 2 — $v$ zirvəsi qara rəngdədir, o və bütün onun nəsilləri tam işlənib.

Yonlü qrafda dövr mövcuddur, əgər boz rəngli zirvəyə gedən bir kənar tapılması ilə dərinlik üzrə axtarışda aşkarlansa.

Nümunə

Problem statementdə təqdim olunan qrafların nümunələri aşağıdakı kimidir:

Algoritmin İcraatı

Həmkarlıq matrisi $g$ və zirvələrin vəziyyətləri massivini $u se d$ elan edək.

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

dfs funksiyası qrafda dərinlik üzrə keçidi $v$ zirvəsindən başlayaraq yerinə yetirir.

void dfs(int v)
{

Zirvəni $v$ boz rəng kimi qeyd edirik, biz ona daxil olduq.

  used[v] = 1;

Vəziyyəti $v$ zirvəsindən getmək mümkün olan bütün zirvələri yoxlayırıq.

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

$v$ -dən $i$ -yə kənar mövcuddur, əgər $g [v] [i] = 1$ g[v][i] = 1.

    if (g[v][i])
    {

Əgər zirvə $i$ boz rəngdədirsə, dərinlik üzrə axtarışda boz zirvəyə daxil olduq — dövr aşkarlanmışdır.

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

Əgər zirvə $i$ ağdırsa, o hələ ziyarət edilməyib. Ondan dərinlik üzrə axtarışa davam edirik.

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

Əgər zirvə $i$ qaradırsa, heç nə etmirik.

$v$ zirvəsinin bütün oğullarının işləməsi bitdikdən sonra, onu qara kimi qeyd edirik.

  used[v] = 2;
}

Proqramın əsas hissəsi. Həmkarlıq matrisini oxuyuruq.

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

Yonlü qrafda dərinlik üzrə axtarışı (əlçatan olmayan kimi) işə salırıq.

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

Cavabı çıxarırıq.

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

Java icrası

import java.util.*;

public class Main
{
  static int g[][], used[];
  static int n, flag;
  static void dfs(int v)
  {
    // boş zirvəni qeyd et, v-yə giriş et
    used[v] = 1;

    // biz v-dən i-yə getməyə çalışırıq, i = 1,2,...,n
    for (int i = 1; i <= n; i++)
      // əgər v-dən i-yə kənar varsa
      if (g[v][i] == 1)
      {
         // əgər zirvə i boz rəngdədirsə, dövr ilə qarşılaşılacaq
         if (used[i] == 1) flag = 1;
         // əgər zirvə i ziyarət edilməyibsə, oradan dfs-i işə salın
         else if (used[i] == 0) dfs(i);
        // əgər zirvə i qara (used[i] = 2)dirsə, heç nə etmirik
      }
    // zirvə v-ni qara qeyd et, ondan çıxış et
    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;
    // yonlu qrafda bağlı olmayan qraf kimi dfs işə salın
    for (int i = 1; i <= n; i++)
      if (used[i] == 0) dfs(i);

    System.out.println(flag);    
  }
}

Java