Sytuację w zadaniu można zamodelować grafem skierowanym o $N$ wierzchołkach. Każdy wierzchołek $v$ odpowiada jednej postaci z serialu i wychodzi z niego jedna skierowana krawędź do wierzchołka $u$ , jeśli postać $v$ kocha postać $u$ . Chcemy zmienić wierzchołki docelowe minimalnej liczby wierzchołków tak, aby każdy wierzchołek znajdował się na skierowanym cyklu długości 2.

Ponieważ z każdego wierzchołka wychodzi dokładnie jedna skierowana krawędź, nasz graf ma specjalną postać: każda jego słabo spójna składowa jest skierowanym cyklem (być może długości 1), do którego mogą być podczepione skierowane drzewa.

Przygotowanie

Na początek zauważamy, że jeśli $N$ jest nieparzyste, to nie da się połączyć wierzchołków w pary, zatem rozwiązanie nie istnieje. Dalej zakładamy, że $N$ jest parzyste.

Wierzchołki na wejściu podane są nie w postaci numerów, ale w postaci napisów. Na początek wygodnie nam będzie zamienić je na liczby od $0$ do $N - 1$ :

const int N = 110000;
int n,par[N],vis[N];
char s1[11],s2[11];
map<ll,int> m;
vector<int> adjT[N];

int encode(const char* s) {
  ll val = 0;
  while (*s) {
    val = 27*val + *s++ - 'a'+1;
  }
  if (!m.count(val)) {
    int s = m.size();
    m[val] = s;
  }
  return m[val];
}


int main() {
  scanf("%d",&n);

  if (n%2) {
    printf("-1\n");
    return 0;
  }

  REP(i,n) {
    scanf("%s%s",s1,s2);
    int v1 = encode(s1), v2 = encode(s2);
    par[v1] = v2;
    if (v1 != v2) adjT[v2].push_back(v1);
  }

Same cykle

W podzadaniu 2 mamy dodatkowy warunek, że „każdy jest przez kogoś kochany”, to znaczy, że do każdego wierzchołka wchodzi co najmniej jedna krawędź. Ponieważ krawędzi jest $N$ (bo z każdego wierzchołka wychodzi dokładnie jedna), z tego wynika, że do każdego wierzchołka wchodzi dokładnie jedna krawędź.

Zatem graf ma jeszcze prostszą postać: składa się ze skierowanych cykli (być może długości 1).

Rozważmy pojedynczy cykl. Jeśli ma on długość 1, to musimy zmienić krawędź wychodzącą z jego pojedynczego wierzchołka. Jeśli ma on długość 2, to nie musimy nic robić.

Niech więc cykl ten ma długość $k > 2$ . Jeżeli zostawimy jakąś krawędź $v_{i} \to v_{i + 1}$ , to będziemy musieli zmienić krawędź w wierzchołku $v_{i + 1}$ z krawędzi $v_{i + 1} \to v_{i + 2}$ na krawędź $v_{i + 1} \to v_{i}$ . Zatem dla każdej krawędzi zostawionej, kolejna na cyklu musi być zmieniona. To pokazuje, że możemy zostawić co najwyżej $⌊ k / 2 ⌋$ krawędzi.

Okazuje się, że można uzyskać taki wynik. Jeśli $k$ jest parzyste, zostawiamy co drugą krawędź, tworząc $k / 2$ cykli długości 2. Jeśli $k$ jest nieparzyste, jeden wierzchołek zostawiamy do sparowania z wierzchołkiem spoza cyklu, a pozostałe $⌊ k / 2 ⌋$ wierzchołków parujemy w cykle długości 2.

Wystarczy zatem dla każdego cyklu wyznaczyć jego długość $k$ i jeśli $k \neq 2$ , dodajemy do wyniku $⌈ k / 2 ⌉$ :

  int ans = 0;

  REP(i,n) if (!vis[i]) {
    int j = i, len = 0;
    do {
      vis[j] = 1;
      ++len;
      j = par[j];
    } while (j != i);

    if (len != 2) {
      ans += (len + 1) / 2;
    }
  }

Rozwiązanie działa w czasie $O (N)$ .

Bez cykli

W podzadaniu 3 mamy inny warunek upraszczający postać grafu: nie ma w nim cykli dłuższych niż 1. Zatem każda słabo spójna składowa jest wierzchołkiem-cyklem długości 1, do którego popodczepiane są skierowane drzewa. Można na to równoważnie patrzeć jak na pojedyncze drzewo skierowane, w którego korzeniu mamy cykl.

Skoro mamy optymalizować liczbę zmienionych krawędzi w drzewie, spróbujmy do tego wykorzystać programowanie dynamiczne na drzewie.

Niech $n i e [v]$ oznacza minimalną liczbę krawędzi, które trzeba zmienić w wierzchołkach poddrzewa zaczepionego w $v$ , jeśli krawędź z wierzchołka $v$ nie może zostać (czyli też jest zmieniana). Zmienna $t a k [v]$ oznacza analogiczny wynik, jeśli krawędź z wierzchołka $v$ może zostać.

Dla liścia mamy $t a k [v] = 0$ oraz $n i e [v] = 1$ .

Dla wierzchołka wewnętrznego $v$ , jeśli jego krawędź zostaje, to żadna krawędź prowadząca do niego z jego synów nie może zostać. Zatem $t a k [v] = S = \sum_{i} n i e [u_{i}],$ gdzie suma jest po dzieciach $u_{i}$ wierzchołka $v$ .

Jeśli krawędź nie zostaje, to albo płacimy $1 + S$ , albo zostaje jedna z krawędzi $u_{i} \to v$ i wtedy płacimy $1 + S - n i e [u_{i}] + t a k [u_{i}]$ . Bierzemy zatem:

$n i e [v] = 1 + S + min (0, min_{i} (t a k [u_{i}] - n i e [u_{i}])) .$

int tak[N],nie[N];

void dfs(int v) {
  if (adjT[v].empty()) {
    tak[v] = 0;
    nie[v] = 1;
  } else {

    int sumnie = 0;
    for (int u : adjT[v]) {
      dfs(u);
      sumnie += nie[u];
    }

    tak[v] = sumnie;
    nie[v] = 1 + sumnie;

    for (int u : adjT[v]) {
      nie[v] = min(nie[v], 1 + sumnie - nie[u] + tak[u]);
    }
  }
}

Wynikiem jest oczywiście suma $n i e [v]$ po wierzchołkach będących korzeniami spójnych składowych:

  int ans = 0;

  REP(i,n) if (par[i] == i) {
    dfs(i);
    ans += nie[i];
  }

Całe rozwiązanie działa w czasie $O (N)$ .

Ogólna postać

W ogólnym przypadku spójna składowa ma postać cyklu z podoczepianymi drzewami. Możemy sprowadzić ten przypadek do przypadku pojedynczego drzewa. W tym celu wybieramy dowolną krawędź na cyklu i rozważamy dwa przypadki: krawędź zostaje lub nie. W obu z nich rozcinamy cykl na tej krawędzi i uruchamiamy poprzedni algorytm.

Czas działania taki sam: $O (N)$ .