shelf[i] — код товара на позиции i. Есть план выкладки plan той же длины: на позиции i должен стоять товар plan[i].
Переставлять товары можно не как угодно, а только по разрешённым связям: каждая пара links[k] = [a, b] позволяет поменять местами товары на позициях a и b. Каждую связь можно использовать сколько угодно раз и в любом порядке.
Несовпадение — это позиция i, где shelf[i] != plan[i]. Верните наименьшее число несовпадений, которого можно добиться перестановками.shelf=[7, 3, 9, 3], plan=[3, 7, 3, 9], links=[[0, 1], [1, 2]] → 2
Позиции 0, 1 и 2 связаны цепочкой, поэтому товары 7, 3, 9 можно расставить между ними как угодно: получим [3, 7, 9, 3]. Совпадают позиции 0 и 1, а на позиции 2 стоит 9 вместо 3 и на позиции 3 — 3 вместо 9. Итого 2 несовпадения.
shelf=[5, 6, 5], plan=[6, 5, 5], links=[] → 2
Менять ничего нельзя: отличаются позиции 0 и 1.
shelf=[4, 8, 2, 6], plan=[6, 2, 8, 4], links=[[0, 3], [2, 1]] → 0
Меняем местами 0 и 3, затем 1 и 2 — полка совпадает с планом полностью.
len(shelf) = len(plan) = n ≤ 10⁵shelf[i], plan[i] ≤ 10⁵len(links) ≤ 10⁵links[k] = [a, b], 0 ≤ a, b ≤ n − 1, a ≠ bshelf=[7, 3, 9, 3], plan=[3, 7, 3, 9], links=[[0, 1], [1, 2]]
2
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 81 тест на сервере, включая скрытые.