Копії без оригіналів (Розбір)

Копії без оригіналів#544

Розв’язок

Простежимо, з якої початкової картки походить вміст кожної картки.

Нехай $p_{i}$ p_i — номер початкової картки, вміст якої зараз міститься на картці $i$ . Спочатку $p_{i} = i$ p_i=i. Під час операції $(x, y)$ достатньо присвоїти $p_{y} = p_{x}$ p_y=p_x. Самі початкові числа для цього знати не потрібно.

Після виконання всіх операцій число $a_{i}$ a_i мало бути записане спочатку на картці $p_{i}$ p_i. Отже, якщо $p_{i} = p_{j}$ p_i=p_j, але $a_{i} \neq = a_{j}$ a_i\ne a_j, заданий кінцевий вміст неможливий і відповідь дорівнює $- 1$ .

Для перевірки заведемо масив $b$ із $n$ нулів. Значення $b_{j} = 0$ b_j=0 означатиме, що вимог до початкового вмісту картки $j$ ще немає. Це зручно, оскільки всі задані числа додатні.

Переберемо картки $i$ від $1$ до $n$ . Якщо $b_{p_{i}} = 0$ b_{p_i}=0, запишемо $b_{p_{i}} = a_{i}$ b_{p_i}=a_i і збільшимо відповідь на один. Якщо $b_{p_{i}} \neq = 0$ b_{p_i}\ne 0, перевіримо, що $b_{p_{i}} = a_{i}$ b_{p_i}=a_i. У разі невідповідності виведемо $- 1$ .

Якщо суперечностей немає, відповідь дорівнює кількості різних значень серед $p_{1}, p_{2}, \dots, p_{n}$ p_1, p_2, \ldots, p_n.

Доведення правильності

Спочатку значення $p_{i} = i$ p_i=i правильно вказує на джерело вмісту картки $i$ . Копіювання з $x$ на $y$ змінює джерело вмісту картки $y$ на джерело вмісту картки $x$ . Тому присвоєння $p_{y} = p_{x}$ p_y=p_x зберігає правильність усіх значень $p_{i}$ p_i після кожної операції.

Якщо дві кінцеві картки походять з однієї початкової картки, їхній вміст має бути однаковим. Отже, кожна знайдена алгоритмом суперечність справді означає, що заданий кінцевий вміст неможливий.

Якщо суперечностей немає, кожна початкова картка, номер якої зустрічається серед значень $p_{i}$ p_i, обов’язково має бути непорожньою: від неї походить хоча б одна непорожня кінцева картка. Тому відповідь не може бути меншою за кількість таких карток.

Запишемо на кожній із них відповідне число $b_{j}$ b_j, а всі інші початкові картки залишимо порожніми. Після всіх операцій картка $i$ міститиме число $b_{p_{i}} = a_{i}$ b_{p_i}=a_i. Так ми отримаємо потрібний вміст із найменшою можливою кількістю непорожніх карток на початку.

Складність

Кожну операцію та кожну картку опрацьовуємо за сталий час. Часова складність — $O (n + m)$ O(n+m), додаткова пам’ять — $O (n)$ . Операції можна опрацьовувати одразу під час зчитування.