Топологічне сортування (Розбір)

Топологічне сортування орієнтованого графа — це така впорядкованість його вершин, що для кожного ребра u \to v вершина $u$ з'являється в послідовності раніше за вершину $v$. Топологічне сортування існує тоді і тільки тоді, коли граф не містить орієнтованих циклів (тобто є ациклічним).

Розв'яжемо задачу за допомогою пошуку в глибину. Кожній вершині присвоюється колір:

• білий — вершину ще не відвідано;

• сірий — вершину відвідано, але її обробка ще не завершена (вона перебуває в поточному стеку рекурсії);

• чорний — вершину та всі досяжні з неї вершини повністю оброблено.

Спочатку всі вершини білі. Запускаємо пошук в глибину з кожної білої вершини. При вході у вершину фарбуємо її в сірий колір; при виході з неї фарбуємо її в чорний колір і додаємо до списку в цей момент. Порядок вершин у топологічному сортуванні є оберненим до порядку, в якому вони стають чорними: перша повністю оброблена вершина буде останньою в сортуванні, а остання оброблена вершина буде першою.

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

Складність. Кожна вершина та кожне ребро обробляються рівно один раз, тому час виконання становить O(n + m).

Приклад

Граф, наведений у прикладі, має такий вигляд:

Поряд з кожною вершиною $v$ ми розміщуємо мітки d[v] / f[v], де $d[v]$ — час, коли вершина починає оброблятися, а $f[v]$ — час, коли її обробка завершується. Топологічно відсортовані вершини розташовані в порядку спадання значень $f[v]$.

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

Оскільки кількість вершин у графі велика, зберігатимемо граф у вигляді списку суміжності $g$. Для відстеження стану вершин використовуємо масив $used$:

• used[i] = 0, якщо вершину $i$ ще не відвідано (вершина біла);

• used[i] = 1, якщо вершину $i$ відвідано, але її обробка ще не завершена (вершина сіра);

• used[i] = 2, якщо вершину $i$ оброблено (вершина чорна);

Під час виконання пошуку в глибину будемо додавати вершини до масиву $top$ у порядку завершення їх обробки. Після завершення роботи алгоритму масив $top$ міститиме вершини в оберненому порядку топологічного сортування.

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

Функція dfs виконує пошук в глибину, починаючи з вершини $v$.

void dfs(int v)
{

Входимо у вершину $v$ та фарбуємо її в сірий колір.

  used[v] = 1;

Переберемо всі вершини $to$, досяжні з вершини $v$.

  for (int to : g[v])
  {

Якщо орієнтоване ребро (v, to) веде до сірої вершини, це вказує на наявність циклу в графі. У цьому випадку встановлюємо flag = 1.

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

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

    if (used[to] == 0) dfs(to);
  }

Завершуємо обробку вершини $v$. Фарбуємо її в чорний колір і додаємо в кінець масиву $top$.

  used[v] = 2;
  top.push_back(v);
}

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

scanf("%d %d",&n,&m);
g.resize(n+1); used.resize(n+1);

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

Виконуємо пошук в глибину на орієнтованому графі.

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

Якщо під час пошуку в глибину виявлено цикл (flag = 1), виводимо $-1$.

if (flag == 1) printf("-1");
else

Інакше виводимо вершини графа в оберненому порядку їх додавання до масиву $top$.

  for(i = top.size() - 1; i >= 0; i--)
    printf("%d ",top[i]);

printf("\n");

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

Зберігаємо вхідний граф у списку суміжності $g$.

Вхідні степені вершин зберігаємо в масиві InDegree.

Результат топологічного сортування зберігається в масиві $top$.

vector<vector<int> > g;
vector<int> InDegree, top;
deque<int> q;

Зчитуємо кількість вершин $n$ та кількість ребер $m$.

scanf("%d %d",&n,&m);
g.resize(n+1);
InDegree.resize(n+1);

Зчитуємо $m$ ребер графа.

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

Для кожного ребра $(a,b)$ збільшуємо InDegree[b] на $1$.

  InDegree[b]++;
}

Усі вершини з нульовим вхідним степенем додаються до черги $q$.

for(i = 1; i < InDegree.size(); i++)
  if (!InDegree[i]) q.push_back(i);

Продовжуємо виконання алгоритму, поки черга $q$ не стане порожньою.

while(!q.empty())
{

Вилучаємо вершину $v$ з черги та додаємо її в кінець списку топологічного порядку.

  v = q.front(); q.pop_front();
  top.push_back(v);

Видаляємо ребра (v, to) з графа. Для кожного такого ребра зменшуємо вхідний степінь вершини $to$.

  for (int to : g[v])
  {
    InDegree[to]--;

Якщо вхідний степінь вершини $to$ стає нульовим, додаємо її до черги. Потім вона буде розміщена в списку топологічного порядку.

    if (!InDegree[to]) q.push_back(to);
  }
}

Якщо не всі $n$ вершин додано до масиву $top$, тоді граф містить цикл, і топологічне сортування неможливе.

if (top.size() < n) 
  printf("-1\n");
else
{

Інакше виводимо вершини графа в топологічному порядку.

  for (int x : top) printf("%d ", x);
  printf("\n");
}

Реалізація мовою Java — пошук в глибину

import java.util.*;
import java.io.*;

public class Main
{
  static ArrayList<ArrayList<Integer>> g;
  static ArrayList<Integer> top = new ArrayList<Integer>();
  static int used[];
  static int n, m, flag = 0;
    
  static void dfs(int v)
  {
    used[v] = 1;
    for(int i = 0; i < g.get(v).size(); i++)
    {
      int to = g.get(v).get(i);
      if (used[to] == 1) flag = 1;
      if (used[to] == 0) dfs(to);
    }
    used[v] = 2;
    top.add(v);
  }
    
  public static void main(String[] args)
  {
    FastScanner con = new FastScanner(System.in);
    n = con.nextInt();
    m = con.nextInt();
    g = new ArrayList<ArrayList<Integer>>();
    used = new int[n+1];
      
    for (int i = 0; i <= n; i++)
      g.add(new ArrayList<Integer>());

    for (int i = 0; i < m; i++)
    {
      int a = con.nextInt();
      int b = con.nextInt();     
      g.get(a).add(b);
    }
      
    for(int i = 1; i <= n; i++)
      if (used[i] == 0) dfs(i);
      
    if (flag == 1) System.out.println("-1");
    else
      for(int i = top.size() - 1; i >= 0; i--)
        System.out.print(top.get(i) + " ");
    System.out.println();
  }
}	

class FastScanner
{
  BufferedReader br;
  StringTokenizer st;
 
  public FastScanner(InputStream inputStream)
  {
    br = new BufferedReader(new InputStreamReader(inputStream));
    st = new StringTokenizer("");
  }
 
  public String next()
  {
    while (!st.hasMoreTokens())
    {
      try
      {
        st = new StringTokenizer(br.readLine());
      } catch (Exception e)
      {
        return null;
      }
    }
    return st.nextToken();
  }
 
  public int nextInt()
  {
    return Integer.parseInt(next());
  }
}

Реалізація мовою Java — Кана

import java.util.*;
import java.io.*;

public class Main
{
  static ArrayList<ArrayList<Integer>> g;
  static ArrayList<Integer> top;
  static int InDegree[];
  static int n, m, flag = 0;
  
  public static void main(String[] args)
  {
    FastScanner con = new FastScanner(System.in);
    n = con.nextInt();
    m = con.nextInt();
    g = new ArrayList<ArrayList<Integer>>();
    InDegree = new int[n+1];
      
    for (int i = 0; i <= n; i++)
      g.add(new ArrayList<Integer>());

    for (int i = 0; i < m; i++)
    {
      int a = con.nextInt();
      int b = con.nextInt();     
      g.get(a).add(b);
      InDegree[b]++;
    }
      
    Queue<Integer> q = new LinkedList<Integer>();
    for(int i = 1; i <= n; i++)
      if (InDegree[i] == 0) q.add(i);

    top = new ArrayList<Integer>();
    while (!q.isEmpty())
    {
      int v = q.poll();
      top.add(v);
      for (int to : g.get(v))
      {
        InDegree[to]--;
        if (InDegree[to] == 0) q.add(to);
      }
    }

    if (top.size() < n)
    	System.out.println("-1");
      else
      {
        for (int x : top) System.out.print(x + " ");
        System.out.println();
      }
  }
}	

class FastScanner
{
  BufferedReader br;
  StringTokenizer st;
 
  public FastScanner(InputStream inputStream)
  {
    br = new BufferedReader(new InputStreamReader(inputStream));
    st = new StringTokenizer("");
  }
 
  public String next()
  {
    while (!st.hasMoreTokens())
    {
      try
      {
        st = new StringTokenizer(br.readLine());
      } catch (Exception e)
      {
        return null;
      }
    }
    return st.nextToken();
  }
 
  public int nextInt()
  {
    return Integer.parseInt(next());
  }
}

Реалізація мовою Python — пошук в глибину

Збільшуємо глибину рекурсії.

import sys
sys.setrecursionlimit(10000)

Функція dfs виконує пошук в глибину, починаючи з вершини $v$.

def dfs(v):

Входимо у вершину $v$ та фарбуємо її в сірий колір.

  used[v] = 1

Переберемо всі вершини $to$, досяжні з вершини $v$.

  for to in g[v]:

Якщо орієнтоване ребро (v, to) веде до сірої вершини, це вказує на наявність циклу в графі. У цьому випадку встановлюємо flag = 1.

    if used[to] == 1:
      global flag
      flag = 1

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

    if used[to] == 0:
      dfs(to)

Завершуємо обробку вершини $v$. Фарбуємо її в чорний колір і додаємо в кінець масиву $top$.

  used[v] = 2
  top.append(v)

Основна частина програми. Зчитуємо кількість вершин $n$ та кількість ребер $m$.

n, m = map(int, input().split())

Зберігаємо вхідний граф у списку суміжності $g$. Оголошуємо список $used$.

g = [[] for _ in range(n + 1)]
used = [0] * (n + 1)

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

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

Виконуємо пошук в глибину на орієнтованому графі.

flag = 0
top = []
for i in range(1, n + 1):
  if used[i] == 0: dfs(i)

Якщо під час пошуку в глибину виявлено цикл (flag = 1), виводимо $-1$.

if flag == 1:
  print("-1")
else:

Інакше виводимо вершини графа в оберненому порядку їх додавання до масиву $top$.

  for i in range(len(top) - 1, -1, -1):
    print(top[i], end=" ")
  print()

Реалізація мовою Python — Кана

Оголошуємо чергу $q$.

from collections import deque
q = deque()

Зчитуємо кількість вершин $n$ та кількість ребер $m$.

n, m = map(int, input().split())

Зберігаємо вхідний граф у списку суміжності $g$.

Вхідні степені вершин зберігаємо в списку InDegree.

Результат топологічного сортування зберігається в списку $top$.

g = [[] for _ in range(n + 1)]
InDegree = [0] * (n + 1)
top = []

Зчитуємо $m$ ребер графа.

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

Для кожного ребра $(a,b)$ збільшуємо InDegree[b] на $1$.

  InDegree[b] += 1

Усі вершини з нульовим вхідним степенем додаються до черги $q$.

for i in range(1, len(InDegree)):
  if not InDegree[i]: q.append(i)

Продовжуємо виконання алгоритму, поки черга $q$ не стане порожньою.

while q:

Вилучаємо вершину $v$ з черги та додаємо її в кінець списку топологічного порядку.

  v = q.popleft()
  top.append(v)

Видаляємо ребра (v, to) з графа. Для кожного такого ребра зменшуємо вхідний степінь вершини $to$.

  for to in g[v]:
    InDegree[to] -= 1

Якщо вхідний степінь вершини $to$ стає нульовим, додаємо її до черги. Потім вона буде розміщена в списку топологічного порядку.

    if not InDegree[to]: q.append(to)

Якщо не всі $n$ вершин додано до масиву $top$, тоді граф містить цикл, і топологічне сортування неможливе.

if len(top) < n:
  print("-1")
else:

Інакше виводимо вершини графа в топологічному порядку.

  for i in top:
    print(i, end=" ")
  print()