e-olymp 1226. Обмен иностранцами

Задача

Ваша неприбыльная организация координирует программу по обмену студентами. И ей нужна Ваша помощь.

Программа обмена работает следующим образом. Каждый из участников дает информацию о месте своем проживания и месте, куда бы он хотел переехать. Программа считается успешной, если каждый студент найдет для обмена подходящего партнера. Другими словами, если некоторый студент желает переехать из $A$ в $B$, то обязательно должен быть другой студент, который хочет переехать из $B$ в $A$. Это простая задача, если участников программы всего $10$. Но что делать если их будет $100001$?

Входные данные

Первая строка содержит количество тестов $t$. Первая строка каждого теста содержит количество студентов $n$ $(1 ≤ n ≤ 100001)$, за которыми следуют $n$ строк, описывающие данные по обмену. Каждая из этих строк содержит информацию об одном студенте — два целых числа, разделенные пробелом, соответствующих текущему месту проживания студента и месту, куда он желает переехать. Места описываются неотрицательными целыми числами, не большими $10^9$. Ни у одного из кандидатов место проживания и место желаемого переезда не совпадают.

Выходные данные

Для каждого теста в отдельной строке вывести $«YES»$ если существует возможность успешно выполнить программу обмена и $«NO»$ иначе.

Тесты

Входные данные	Выходные данные
2 2 1 2 2 1 2 31 13 13 31	YES YES
1 4 17 3 28 15 15 28 3 17	YES
1 4 17 3 28 15 15 28 3 18	NO
3 2 1 2 3 4 2 47 7 7 47 2 12 34 12 34	NO YES NO

Код программы

#include <iostream>
#include <set>
using namespace std;

multiset <pair <unsigned int, unsigned int>> M;
multiset <pair <unsigned int, unsigned int>>::iterator it;

int main() {
    unsigned int t, n, a, b;
    cin >> t;
    while (t != 0) {
        cin >> n;
        M.clear();
        for (int i = 0; i < n; i++) {
            cin >> a >> b;
            if ((it = M.find (make_pair(b, a))) == M.end()) {
                M.insert (make_pair(a, b));
            } else M.erase(it);
        }
        (M.empty()) ? cout << "YES" << endl : cout << "NO" << endl;
        t--;
    }
    
    return 0;
}

#include <iostream>

#include <set>

using namespace std;

multiset <pair <unsigned int, unsigned int>> M;

multiset <pair <unsigned int, unsigned int>>::iterator it;

int main() {

unsigned int t, n, a, b;

cin >> t;

while (t != 0) {

cin >> n;

M.clear();

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

cin >> a >> b;

if ((it = M.find (make_pair(b, a))) == M.end()) {

M.insert (make_pair(a, b));

} else M.erase(it);

}

(M.empty()) ? cout << "YES" << endl : cout << "NO" << endl;

t--;

}

return 0;

}

Решение задачи

После задания переменной $n$ (количества студентов) очищаем мультимножество $M$. Для каждой пары $(a, b)$ нашего мультимножества проверяем, есть ли в нем пара $(b, a)$:
1. Если есть, то удаляем пару $(b, a)$.
2. Если нет, то вставляем $(a, b)$.
Если в конце мультимножество $M$ пустое, то у каждой пары $(a, b)$ существует соответствующая ей пара $(b, a)$, следовательно обмен студентами может быть произведен успешно.