Обмін іноземцями (Розбір)

Для успішної реалізації програми обміну необхідно, щоб для кожного студента, який бажає переїхати з $A$ в $B$, існував інший студент, який бажає переїхати з $B$ в $A$. Тобто кожна пара $(A,B)$ повинна мати відповідну їй зворотну пару $(B,A)$. При цьому однакові пари можуть зустрічатися кілька разів.

Для збереження пар будемо використовувати мультимножину. Опишемо алгоритм роботи програми:

• для кожної вхідної пари $(А,В)$ перевіряємо, чи міститься в мультимножині пара $(B,A)$.

• якщо така пара знайдена, то видаляємо її з мультимножини, тим самим формуючи коректну пару обміну;

• якщо зворотної пари немає, додаємо поточну пару $(A,B)$ в мультимножину.

Після обробки всіх студентів можливі два випадки:

• мультимножина порожня — це означає, що для кожної пари $(A,B)$ знайшлася відповідна зворотна пара $(B,A)$, і програму обміну можна успішно здійснити;

• мультимножина не порожня — значить, деякі студенти залишились без підходящого партнера, і програма обміну неможлива.

Залежно від цього виводиться відповідь "YES" або "NO".

Приклад

У першому тесті для кожної пари $(A,B)$ знайдеться відповідна зворотна пара $(B,A)$. У другому тесті жодне бажання студента не може бути виконане.

Реалізація алгоритму

Оголосимо мультимножину пар $s$. У процесі роботи в ній будуть зберігатися тільки ті пари $(А,В)$, для яких ще не знайдено відповідну пару $(В,А)$.

multiset<pair<int,int> > s;

Читаємо кількість тестів $t$.

scanf("%d",&t);

Послідовно обробляємо $t$ тестів.

while (t--)
{

Читаємо кількість студентів $n$.

  scanf("%d", &n); 

Перед обробкою чергового тесту очищаємо мультимножину.

  s.clear();

Послідовно обробляємо бажання студентів.

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

Читаємо пару $(a,b)$. Шукаємо студента з протилежним напрямком переїзду.

    scanf("%d %d", &a, &b);
    auto it = s.find({ b, a });

Якщо зворотна пара не знайдена, поточна пара $(a,b)$ додається в мультимножину $s$.

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

Таким чином, у $s$ завжди зберігаються тільки ті пари, для яких поки не знайдено відповідність.

    if (it == s.end()) s.insert({ a, b });
    else s.erase(it);
  }

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

  if (s.empty()) printf("YES\n");
  else printf("NO\n");
}