Cırtdanlar (Həll təhlili)

Məsələni istiqamətlənmiş qrafla əlaqələndirək. Qrafın təpələri cırtdanlardır və hər bir ifadə bir kənar müəyyən edir. Əgər s_1 cırtdanı s_2 cırtdanından qısadırsa (yəni s_1 < s_2), biz s_1 \to s_2 istiqamətlənmiş kənarını əlavə edirik. s_1 > s_2 ifadəsi s_2 < s_1 ifadəsinə ekvivalentdir və s_2 \to s_1 kənarını müəyyən edir. Beləliklə, hər bir kənar qısa cırtdandan uzun cırtdana doğru istiqamətlənir.

Cırtdan adları sətirlərdir, ona görə ilk əvvəl hər bir ada unikal tam ədəd təpə indeksi təyin edirik.

İfadələr ziddiyyətli olduqda. Fərz edək ki, qrafda v_1 \to v_2 \to \ldots \to v_k \to v_1 dövrəsi var. Onda v_1 cırtdanı v_2-dən qısadır, v_2 cırtdanı v_3-dən qısadır, $\dots$, v_k cırtdanı v_1-dən qısadır. Tranzitivlik üzrə, v_1 cırtdanı özündən qısadır ki, bu da mümkün deyil. Beləliklə, cırtdanlardan ən azı biri yalan deyib.

Əksinə, əgər qraf tsikl olmayandırsa (asiklikdirsə), onda onun topoloji sıralaması mövcuddur — təpələrin elə bir ardıcıllığı ki, hər bir kənar əvvəlki təpədən sonrakı təpəyə gedir. Cırtdanlara topoloji sırada 1, 2, 3, \ldots hündürlüklərini təyin edək. Onda hər bir s_1 \to s_2 kənarı üçün s_1 < s_2 bərabərsizliyi doğru olur, yəni bütün ifadələr eyni zamanda doğrudur.

Beləliklə, cavab "impossible" olur yalnız və yalnız o halda ki, qurulmuş qrafda tsikl mövcud olsun.

Tsiklin tapılması. İstiqamətlənmiş qrafda tsikl tapmaq üçün üç rəngli təpələrlə dərinliyə görə axtarışdan istifadə edirik:

• ağ təpə (used[v] = 0) hələ ziyarət edilməyib;

• boz təpə (used[v] = 1) emal olunur: axtarış ora daxil olub, lakin hələ çıxmayıb. Boz təpələr axtarışın kökündən cari təpəyə qədər olan yolu təşkil edir;

• qara təpə (used[v] = 2) tam emal olunub: ondan əlçatan bütün təpələr artıq ziyarət edilib.

Əgər axtarış zamanı cari $v$ təpəsindən çıxan v \to to kənarı boz $to$ təpəsinə aparırsa, deməli $to$ kökdən $v$-yə qədər olan cari yolda yerləşir. v \to to kənarı ilə birlikdə bu yol tsikl təşkil edir. Qara təpəyə gedən kənar tsikl yaratmır: qara təpədən $v$-yə qayıtmaq mümkün deyil, əks halda $v$ daha əvvəl ziyarət edilmiş olardı.

Qraf əlaqəli olmaya bilər, ona görə dərinliyə görə axtarışı ziyarət edilməmiş hər bir təpədən başladırıq.

Misal

Məsələnin şərtindəki misallara uyğun qraflar aşağıdakı kimidir (solda — birinci misalın qrafı, sağda — ikincinin):

Birinci qraf Dori $\to$ Kili $\to$ Balin $\to$ Dori tsiklini ehtiva edir. Bu o deməkdir ki, Dori Kilidən qısadır, Kili Balindən qısadır, Balin isə Doridən qısadır. Onda Dori özündən qısadır, bu da ifadələrin ziddiyyətli olduğunu göstərir və cavab "impossible" olur.

İkinci qraf asiklikdir. Onun topoloji sıralaması Kili, Balin, Dori şəklindədir. Cırtdanlara bu ardıcıllıqla hündürlük təyin etsək (Kili $<$ Balin $<$ Dori), bütün üç ifadənin eyni zamanda doğru olduğunu görərik. Cavab "possible" olur.

Birinci test üçün qrafın necə qurulduğuna baxaq. Hər ad girişdə ilk dəfə göründüyü sıraya görə indeks alır. Birinci ad Doridir, o, $0$ indeksini alır. Sonra Balin gəlir — $1$ indeksi. İkinci ifadədə Balin adı artıq indeks almışdır, buna görə yeni indeks yalnız Kiliyə təyin edilir — $2$ indeksi. Beləliklə, name\_to\_id[Dori] = 0, name\_to\_id[Balin] = 1, name\_to\_id[Kili] = 2 və qraf 1 \to 0, 2 \to 1 və 0 \to 2 kənarlarını ehtiva edir.

Dərinliyə görə axtarışı simulyasiya edək. $dfs(0)$ çağırırıq: $0$ təpəsi (Dori) boz olur. 0 \to 2 kənarı ilə ağ $2$ təpəsinə (Kili) keçirik, o boz olur. 2 \to 1 kənarı ilə ağ $1$ təpəsinə (Balin) keçirik, o da boz olur. 1 \to 0 kənarı $1$ təpəsindən çıxır və boz $0$ təpəsinə aparır. Tsikl tapılır, ona görə flag = 1 təyin edirik.

Alqoritmin reallaşdırılması

İstiqamətlənmiş qrafı $g$ qonşuluq siyahısı kimi saxlayaq. $used$ massivi dərinliyə görə axtarış zamanı təpələrin rənglərini saxlayır: $0$ — ağ, $1$ — boz, $2$ — qara. name\_to\_id xəritəsi cırtdanın adını təpə indeksinə uyğunlaşdırır: $s$ adlı cırtdan name\_to\_id[s] təpəsinə uyğun gəlir.

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

get_id funksiyası $name$ adlı cırtdana uyğun gələn təpənin indeksini qaytarır. İndekslər adların ilk dəfə göründüyü sıraya görə təyin edilir: $0$-dan id - 1-ə qədər, burada $id$ indiyə qədər rast gəlinmiş fərqli cırtdanların sayıdır.

int get_id(string name)
{

Əgər $name$ adlı cırtdana artıq rast gəlinibsə, əvvəl ona təyin edilmiş indeksi qaytarırıq.

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

Əks halda, $name$ adlı cırtdana növbəti $id$ indeksini təyin edirik və $id$-ni $1$ vahid artırırıq.

  return name_to_id[name] = id++;
}

dfs funksiyası $v$ təpəsindən başlayaraq dərinliyə görə axtarış aparır. $v$ təpəsinə daxil olduqda o boz olur.

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

(v, to) kənarını nəzərdən keçirək. Əgər o boz təpəyə aparırsa, tsikl tapılıb. flag = 1 təyin edib axtarışı dayandırırıq.

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

Əgər $to$ təpəsi hələ ziyarət edilməyibsə (ağdırsa), dərinliyə görə axtarışı ondan davam etdiririk.

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

$v$-dən əlçatan bütün təpələr emal olunduqdan sonra, $v$ təpəsi qara olur.

  used[v] = 2;
}

Proqramın əsas hissəsi. İfadələrin sayı $n$-i oxuyuruq. Fərqli cırtdanların sayı 10^4-dən çox deyil, ona görə qrafda ən çoxu bu qədər təpə var. Qonşuluq siyahısı və rəng massivi üçün yaddaş ayırırıq; əvvəlcə bütün təpələr ağdır.

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

Cırtdanların nömrələnməsi $0$-dan başlayır.

id = 0;

$n$ ifadəni emal edək. Onların hər biri qrafın bir istiqamətlənmiş kənarını müəyyən edir.

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

s_1 < s_2 və ya s_1 > s_2 formasında ifadəni oxuyuruq: $l$ adı, $op$ işarəsi və $r$ adı.

  cin >> l >> op >> r;

$l$ və $r$ cırtdanlarına uyğun gələn $u$ və $v$ təpələrinin indekslərini tapırıq.

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

Kənar qısa cırtdandan uzun cırtdana doğru istiqamətlənir. Əgər l < r olarsa, u \to v kənarını əlavə edirik, əks halda v \to u kənarını əlavə edirik.

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

Əgər qrafda tsikl tapılarsa, $flag$ dəyişəni $1$ olur.

flag = 0;

Qraf əlaqəli olmaya bilər, ona görə dərinliyə görə axtarışı ziyarət edilməmiş hər bir təpədən başladırıq. Təpələr $0$-dan id - 1-ə qədər nömrələnib. Tsikl tapılan kimi axtarışı dayandırırıq.

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

Əgər tsikl tapılarsa, ifadələr ziddiyyətlidir — "impossible" çap edilir, əks halda "possible" çap edilir.

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

Java reallaşdırılması

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