Gnomi#7945

Gnomi (Editoriale)

Associamo al problema un grafo orientato. I vertici del grafo sono gli gnomi, e ogni affermazione definisce un arco. Se lo gnomo $s_{1}$ s_1 è più basso dello gnomo $s_{2}$ s_2 (cioè $s_{1} < s_{2}$ s_1 < s_2), aggiungiamo un arco orientato $s_{1} \to s_{2}$ s_1 \to s_2. L'affermazione $s_{1} > s_{2}$ s_1 > s_2 equivale a $s_{2} < s_{1}$ s_2 < s_1 e definisce l'arco $s_{2} \to s_{1}$ s_2 \to s_1. Quindi, ogni arco è orientato da uno gnomo più basso verso uno più alto.

I nomi degli gnomi sono stringhe, quindi per prima cosa assegniamo a ciascun nome un indice intero univoco di vertice.

Quando le affermazioni sono contraddittorie. Supponiamo che il grafo contenga un ciclo $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. Allora $v_{1}$ v_1 è più basso di $v_{2}$ v_2, $v_{2}$ v_2 è più basso di $v_{3}$ v_3, $\dots$ , $v_{k}$ v_k è più basso di $v_{1}$ v_1. Per transitività, lo gnomo $v_{1}$ v_1 è più basso di se stesso, il che è impossibile. Quindi, almeno uno degli gnomi ha mentito.

Viceversa, se il grafo è aciclico, esso possiede un ordinamento topologico — un ordinamento dei vertici in cui ogni arco va da un vertice precedente a uno successivo. Assegniamo agli gnomi le altezze $1, 2, 3, \dots$ 1, 2, 3, \ldots secondo l'ordinamento topologico. Allora $s_{1} < s_{2}$ s_1 < s_2 vale per ogni arco $s_{1} \to s_{2}$ s_1 \to s_2, cioè tutte le affermazioni sono vere simultaneamente.

Quindi, la risposta è "impossible" se e solo se il grafo costruito contiene un ciclo.

Individuazione del ciclo. Per trovare un ciclo in un grafo orientato, utilizziamo la ricerca in profondità (depth-first search) con tre colori per i vertici:

un vertice bianco ( $u se d [v] = 0$ used[v] = 0) non è ancora stato visitato;
un vertice grigio ( $u se d [v] = 1$ used[v] = 1) è in corso di elaborazione: la ricerca vi è entrata ma non ne è ancora uscita. I vertici grigi formano il percorso dalla radice della ricerca fino al vertice corrente;
un vertice nero ( $u se d [v] = 2$ used[v] = 2) è completamente elaborato: tutti i vertici raggiungibili da esso sono già stati visitati.

Se durante la ricerca un arco $v \to t o$ v \to to dal vertice corrente $v$ porta a un vertice grigio $t o$ , allora $t o$ si trova sul percorso corrente dalla radice a $v$ . Insieme all'arco $v \to t o$ v \to to, questo percorso forma un ciclo. Un arco verso un vertice nero non crea un ciclo: da un vertice nero è impossibile tornare a $v$ , altrimenti $v$ sarebbe stato visitato prima.

Il grafo può essere disconnesso, quindi avviamo una ricerca in profondità a partire da ogni vertice non ancora visitato.

Esempio

I grafi corrispondenti agli esempi dell'enunciato del problema sono i seguenti (a sinistra — il grafo del primo esempio, a destra — del secondo):

Il primo grafo contiene il ciclo Dori $\to$ Kili $\to$ Balin $\to$ Dori. Ciò significa che Dori è più basso di Kili, Kili è più basso di Balin, e Balin è più basso di Dori. Allora Dori è più basso di se stesso, quindi le affermazioni sono contraddittorie e la risposta è "impossible".

Il secondo grafo è aciclico. Il suo ordinamento topologico è Kili, Balin, Dori. Assegnando agli gnomi le altezze in questo ordine (Kili $<$ Balin $<$ Dori), otteniamo che tutte e tre le affermazioni valgono simultaneamente. La risposta è "possible".

Consideriamo come viene costruito il grafo per il primo test. Ogni nome riceve un indice secondo l'ordine della sua prima comparsa nell'input. Il primo nome è Dori, che riceve l'indice $0$ . Poi viene Balin — indice $1$ . Nella seconda affermazione, il nome Balin ha già un indice, quindi un nuovo indice viene assegnato solo a Kili — indice $2$ . Quindi, $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, e il grafo contiene gli archi $1 \to 0$ 1 \to 0, $2 \to 1$ 2 \to 1 e $0 \to 2$ 0 \to 2.

Simuliamo la ricerca in profondità. Chiamiamo $df s (0)$ : il vertice $0$ (Dori) diventa grigio. Lungo l'arco $0 \to 2$ 0 \to 2 ci spostiamo al vertice bianco $2$ (Kili), che diventa grigio. Lungo l'arco $2 \to 1$ 2 \to 1 ci spostiamo al vertice bianco $1$ (Balin), che diventa anch'esso grigio. L'arco $1 \to 0$ 1 \to 0 esce dal vertice $1$ e porta al vertice grigio $0$ . Viene trovato un ciclo, quindi impostiamo $f l a g = 1$ flag = 1.

Implementazione dell'algoritmo

Memorizziamo il grafo orientato come lista di adiacenza $g$ . L'array $u se d$ memorizza i colori dei vertici durante la ricerca in profondità: $0$ — bianco, $1$ — grigio, $2$ — nero. La mappa $nam e_t o_i d$ name\_to\_id associa il nome di uno gnomo a un indice di vertice: lo gnomo di nome $s$ corrisponde al vertice $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;

La funzione get_id restituisce l'indice del vertice corrispondente allo gnomo di nome $nam e$ . Gli indici vengono assegnati nell'ordine in cui i nomi compaiono per la prima volta: da $0$ a $i d - 1$ id - 1, dove $i d$ è il numero di gnomi distinti incontrati finora.

int get_id(string name)
{

Se lo gnomo di nome $nam e$ è già stato incontrato, restituisce l'indice che gli è stato assegnato in precedenza.

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

Altrimenti, assegna il successivo indice $i d$ allo gnomo di nome $nam e$ e incrementa $i d$ di $1$ .

  return name_to_id[name] = id++;
}

La funzione dfs esegue una ricerca in profondità a partire dal vertice $v$ . All'ingresso nel vertice $v$ , esso diventa grigio.

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

Consideriamo l'arco $(v, t o)$ (v, to). Se porta a un vertice grigio, è stato trovato un ciclo. Impostiamo $f l a g = 1$ flag = 1 e interrompiamo la ricerca.

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

Se il vertice $t o$ non è ancora stato visitato (è bianco), proseguiamo la ricerca in profondità a partire da esso.

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

Dopo che tutti i vertici raggiungibili da $v$ sono stati elaborati, il vertice $v$ diventa nero.

  used[v] = 2;
}

La parte principale del programma. Leggiamo il numero di affermazioni $n$ . Il numero di gnomi distinti non supera $1 0^{4}$ 10^4, quindi il grafo ha al massimo questo numero di vertici. Allochiamo memoria per la lista di adiacenza e l'array dei colori; inizialmente tutti i vertici sono bianchi.

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

La numerazione degli gnomi inizia da $0$ .

id = 0;

Elaboriamo le $n$ affermazioni. Ognuna di esse definisce un arco orientato del grafo.

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

Leggiamo un'affermazione della forma $s_{1} < s_{2}$ s_1 < s_2 o $s_{1} > s_{2}$ s_1 > s_2: il nome $l$ , il segno $o p$ e il nome $r$ .

  cin >> l >> op >> r;

Troviamo gli indici $u$ e $v$ dei vertici corrispondenti agli gnomi $l$ e $r$ .

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

Un arco è orientato da uno gnomo più basso verso uno più alto. Se $l < r$ l < r, aggiungiamo l'arco $u \to v$ u \to v, altrimenti aggiungiamo l'arco $v \to u$ v \to u.

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

La variabile $f l a g$ diventa $1$ se viene trovato un ciclo nel grafo.

flag = 0;

Il grafo può essere disconnesso, quindi avviamo una ricerca in profondità a partire da ogni vertice non ancora visitato. I vertici sono numerati da $0$ a $i d - 1$ id - 1. Non appena viene trovato un ciclo, interrompiamo la ricerca.

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

Se viene trovato un ciclo, le affermazioni sono contraddittorie — stampiamo "impossible", altrimenti stampiamo "possible".

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

Implementazione in 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