Пошук циклу#2270

Пошук циклу (Розбір)

Виконаємо серію перетворень графа в глибину. Для цього з кожної вершини, в якій ми ще не були, запустимо пошук в глибину. При вході в вершину будемо зафарбовувати її в сірий колір, а при виході — в чорний. Якщо під час пошуку ми спробуємо перейти в вершину, вже зафарбовану в сірий колір, це означатиме, що знайдений цикл.

Для відновлення циклу необхідно зберігати послідовність вершин в порядку їх обходу. Наприклад, якщо масив обходу містить вершини $(2, 6, 3, 5, 4, 3)$ (2, 6, 3, 5, 4, 3), то шуканим циклом буде $(3, 5, 4)$ (3, 5, 4).

Приклад

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

Біля кожної вершини вказано поточний стан масиву $p a t h$ .

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

Список суміжності графа зберігається в векторі $g$ . У масиві $p a t h$ зберігаємо послідовність вершин у порядку обходу в глибину.

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

Функція dfs реалізує пошук в глибину з вершини $v$ . При вході в вершину $v$ зафарбовуємо її в сірий колір $(u se d [v] = 1)$ (used[v] = 1), а при виході — в чорний $(u se d [v] = 2)$ (used[v] = 2). Глобальна змінна $f l a g$ вказує на наявність циклу: $f l a g = 1$ flag = 1 означає, що цикл знайдено, $f l a g = 0$ flag = 0 означає, що циклу немає.

void dfs(int v)
{

Якщо цикл вже був знайдений $(f l a g = 1)$ (flag = 1), продовжувати пошук сенсу немає.

  if (flag == 1) return;

Вершину $v$ відзначаємо сірою та додаємо в масив $p a t h$ .

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

Перебираємо вершини $t o$ , суміжні з $v$ .

  for (int to : g[v])

Цикл вважається знайденим, якщо пошук вглиб намагається піти у сіру вершину (у вершину $t o$ , для якої $u se d [t o] = 1)$ used[to] = 1).

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

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

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

Після завершення обробки вершини $v$ відзначаємо її чорним кольором. Видаляємо вершину $v$ з масиву $p a t h$ .

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

Основна частина програми. Читаємо список ребер та будуємо список суміжності графа.

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);
}

C++

Запускаємо серію обходів в глибину. Якщо вершина $i$ ще не оброблена $(u se d [i] = 0)$ (used[i] = 0), запускаємо з неї пошук в глибину. Якщо при виконанні чергового виклику функції dfs значення змінної $f l a g$ стає рівною $1$ (виявлено цикл в графі), припиняємо подальший пошук.

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

Якщо $f l a g = 1$ flag = 1, це означає, що цикл був знайдений. В такому випадку виводимо його, виходячи з інформації в масиві $p a t h$ .

if (flag == 1)
{

Цикл знайдено і завершується в вершині $c f in = p a t h [p a t h . s i z e () - 1]$ cfin = path[path.size() - 1].

  cfin = path.back();

Рухаємося змінною $cs t a r t$ назад по масиву $p a t h$ , щоб знайти ту ж вершину $c f in$ — точку, в якій починається цикл.

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

Виводимо повідомлення про наявність циклу та сам цикл.

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

Інакше $(f l a g = 0)$ (flag = 0) циклів у графі немає.

else printf("NO\n");

Java реалізація

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();
  }
}

Java