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.
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); }
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 $\lfloor k / 2 \rfloor$ 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 $\lfloor k / 2 \rfloor$ 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 $\lceil k/2 \rceil$:
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)$.
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 $nie[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 $tak[v]$ oznacza analogiczny wynik, jeśli krawędź z wierzchołka $v$ może zostać.
Dla liścia mamy $tak[v]=0$ oraz $nie[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 $$tak[v] = S = \sum_{i} nie[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 - nie[u_i] + tak[u_i]$. Bierzemy zatem:
$$nie[v] = 1 + S + \min(0,\ \min_{i}( tak[u_i] - nie[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 $nie[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)$.
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)$.