Гноми (Розбір)

Пов'яжемо із задачею орієнтований граф. Вершинами графа є гноми, а кожне твердження визначає ребро. Якщо гном $s_{1}$ s_1 нижчий за гнома $s_{2}$ s_2 (тобто $s_{1} < s_{2}$ s_1 < s_2), додаємо орієнтоване ребро $s_{1} \to s_{2}$ s_1 \to s_2. Твердження $s_{1} > s_{2}$ s_1 > s_2 еквівалентне $s_{2} < s_{1}$ s_2 < s_1 і визначає ребро $s_{2} \to s_{1}$ s_2 \to s_1. Таким чином, кожне ребро спрямоване від нижчого гнома до вищого.

Імена гномів — це рядки, тому спочатку присвоюємо кожному імені унікальний цілочисельний індекс вершини.

Коли твердження суперечливі. Припустимо, граф містить цикл $v_{1} \to v_{2} \to \dots \to v_{k} \to v_{1}$ v_1 \to v_2 \to \ldots \to v_k \to v_1. Тоді $v_{1}$ v_1 нижчий за $v_{2}$ v_2, $v_{2}$ v_2 нижчий за $v_{3}$ v_3, $\dots$ , $v_{k}$ v_k нижчий за $v_{1}$ v_1. За транзитивністю гном $v_{1}$ v_1 нижчий за самого себе, що неможливо. Отже, хоча б один із гномів збрехав.

І навпаки, якщо граф ациклічний, то він має топологічне сортування — впорядкування вершин, в якому кожне ребро йде від попередньої вершини до наступної. Присвоїмо гномам зрости $1, 2, 3, \dots$ 1, 2, 3, \ldots у порядку топологічного сортування. Тоді $s_{1} < s_{2}$ s_1 < s_2 виконується для кожного ребра $s_{1} \to s_{2}$ s_1 \to s_2, тобто всі твердження істинні одночасно.

Отже, відповідь "impossible" тоді і тільки тоді, коли побудований граф містить цикл.

Пошук циклу. Щоб знайти цикл в орієнтованому графі, використовуємо пошук у глибину із трьома кольорами вершин:

біла вершина ( $u se d [v] = 0$ used[v] = 0) ще не відвідана;
сіра вершина ( $u se d [v] = 1$ used[v] = 1) обробляється: пошук зайшов до неї, але ще не вийшов. Сірі вершини утворюють шлях від кореня пошуку до поточної вершини;
чорна вершина ( $u se d [v] = 2$ used[v] = 2) повністю оброблена: всі вершини, досяжні з неї, вже відвідані.

Якщо під час пошуку ребро $v \to t o$ v \to to з поточної вершини $v$ веде до сірої вершини $t o$ , то $t o$ лежить на поточному шляху від кореня до $v$ . Разом із ребром $v \to t o$ v \to to цей шлях утворює цикл. Ребро до чорної вершини не створює цикл: із чорної вершини неможливо повернутися до $v$ , інакше $v$ було б відвідано раніше.

Граф може бути незв'язним, тому запускаємо пошук у глибину з кожної вершини, яка ще не була відвідана.

Приклад

Графи, що відповідають прикладам з умови задачі, виглядають так (зліва — граф першого прикладу, справа — другого):

Перший граф містить цикл Dori $\to$ Kili $\to$ Balin $\to$ Dori. Це означає, що Dori нижчий за Kili, Kili нижчий за Balin, а Balin нижчий за Dori. Тоді Dori нижчий за самого себе, тому твердження суперечливі і відповідь "impossible".

Другий граф ациклічний. Його топологічне сортування — Kili, Balin, Dori. Присвоївши гномам зрости в цьому порядку (Kili $<$ Balin $<$ Dori), отримуємо, що всі три твердження виконуються одночасно. Відповідь "possible".

Розглянемо, як будується граф для першого тесту. Кожне ім'я отримує індекс у порядку своєї першої появи у вхідних даних. Перше ім'я — Dori, воно отримує індекс $0$ . Далі йде Balin — індекс $1$ . У другому твердженні ім'я Balin вже має індекс, тому новий індекс присвоюється лише Kili — індекс $2$ . Таким чином, $nam e_t o_i d [D or i] = 0$ name\_to\_id[Dori] = 0, $nam e_t o_i d [B a l in] = 1$ name\_to\_id[Balin] = 1, $nam e_t o_i d [K i l i] = 2$ name\_to\_id[Kili] = 2, і граф містить ребра $1 \to 0$ 1 \to 0, $2 \to 1$ 2 \to 1 та $0 \to 2$ 0 \to 2.

Просимулюємо пошук у глибину. Викликаємо $df s (0)$ : вершина $0$ (Dori) стає сірою. По ребру $0 \to 2$ 0 \to 2 переходимо до білої вершини $2$ (Kili), яка стає сірою. По ребру $2 \to 1$ 2 \to 1 переходимо до білої вершини $1$ (Balin), яка також стає сірою. Ребро $1 \to 0$ 1 \to 0 виходить із вершини $1$ і веде до сірої вершини $0$ . Знайдено цикл, тому встановлюємо $f l a g = 1$ flag = 1.

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

Зберігаємо орієнтований граф у вигляді списку суміжності $g$ . Масив $u se d$ зберігає кольори вершин під час пошуку в глибину: $0$ — білий, $1$ — сірий, $2$ — чорний. Словник $nam e_t o_i d$ name\_to\_id зіставляє ім'я гнома з індексом вершини: гному з іменем $s$ відповідає вершина $nam e_t o_i d [s]$ name\_to\_id[s].

vector<vector<int> > g;
vector<int> used;
unordered_map<string, int> name_to_id;

Функція get_id повертає індекс вершини, що відповідає гному з іменем $nam e$ . Індекси присвоюються в порядку першої появи імен: від $0$ до $i d - 1$ id - 1, де $i d$ — кількість різних гномів, зустрінутих на даний момент.

int get_id(string name)
{

Якщо гном з іменем $nam e$ вже зустрічався, повертаємо присвоєний йому раніше індекс.

  if (name_to_id.count(name)) return name_to_id[name];

Інакше присвоюємо гному з іменем $nam e$ наступний індекс $i d$ і збільшуємо $i d$ на $1$ .

  return name_to_id[name] = id++;
}

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

void dfs(int v)
{
  used[v] = 1;
  for (int to : g[v])
  {

Розглянемо ребро $(v, t o)$ (v, to). Якщо воно веде до сірої вершини, знайдено цикл. Встановлюємо $f l a g = 1$ flag = 1 і припиняємо пошук.

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

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

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

Після того, як усі вершини, досяжні з $v$ , оброблені, вершина $v$ стає чорною.

  used[v] = 2;
}

Основна частина програми. Зчитуємо кількість тверджень $n$ . Кількість різних гномів не перевищує $1 0^{4}$ 10^4, тому граф має не більше стільки вершин. Виділяємо пам'ять для списку суміжності та масиву кольорів; спочатку всі вершини білі.

cin >> n;
g.resize(10001); used.resize(10001,0);

Нумерація гномів починається з $0$ .

id = 0;

Обробляємо $n$ тверджень. Кожне з них визначає одне орієнтоване ребро графа.

for (i = 0; i < n; i++)
{

Зчитуємо твердження вигляду $s_{1} < s_{2}$ s_1 < s_2 або $s_{1} > s_{2}$ s_1 > s_2: ім'я $l$ , знак $o p$ та ім'я $r$ .

  cin >> l >> op >> r;

Знаходимо індекси $u$ та $v$ вершин, що відповідають гномам $l$ та $r$ .

  u = get_id(l);
  v = get_id(r);

Ребро спрямоване від нижчого гнома до вищого. Якщо $l < r$ l < r, додаємо ребро $u \to v$ u \to v, інакше додаємо ребро $v \to u$ v \to u.

  if (op == "<")
    g[u].push_back(v);
  else
    g[v].push_back(u);
}

Змінна $f l a g$ стає рівною $1$ , якщо в графі знайдено цикл.

flag = 0;

Граф може бути незв'язним, тому запускаємо пошук у глибину з кожної вершини, яка ще не була відвідана. Вершини нумеруються від $0$ до $i d - 1$ id - 1. Як тільки знайдено цикл, припиняємо пошук.

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

Якщо знайдено цикл, твердження суперечливі — виводимо "impossible", інакше виводимо "possible".

if (flag == 1) printf("impossible\n");
else printf("possible\n");

Реалізація на Java

import java.util.*;

public class Main {
  static List<List<Integer>> g = new ArrayList<>();
  static int[] used;
  static Map<String, Integer> nameToId = new HashMap<>();
  static int id = 0;
  static boolean hasCycle = false;

  static int getId(String name) {
    if (!nameToId.containsKey(name))
      nameToId.put(name, id++);
    return nameToId.get(name);
  }

  static void dfs(int v) {
    used[v] = 1;
    for (int to : g.get(v)) {
      if (used[to] == 1) {
        hasCycle = true;
        return;
      }
      if (used[to] == 0) dfs(to);
    }
    used[v] = 2;
  }
    
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    used = new int[10001];

    for (int i = 0; i < 10001; i++)
       g.add(new ArrayList<>());

    for (int i = 0; i < n; i++) {
      String l = sc.next();
      String op = sc.next();
      String r = sc.next();

      int u = getId(l);
      int v = getId(r);

      if (op.equals("<"))
        g.get(u).add(v);
      else
        g.get(v).add(u);
    }

    for (int i = 0; i < id; i++) {
      if (used[i] == 0) {
        dfs(i);
        if (hasCycle) break;
      }
    }

    System.out.println(hasCycle ? "impossible" : "possible");
  }
}

Java