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

Ваша некоммерческая организация координирует программу обмена студентами и нуждается в помощи.

Программа обмена работает следующим образом: каждый участник указывает своё текущее место жительства и место, куда он хотел бы переехать. Программа считается успешной, если для каждого студента можно найти подходящего партнёра для обмена. Иными словами, если студент хочет переехать из A в B, должен существовать другой студент, желающий переехать из B в A.

Такую проверку легко выполнить, если участников всего , но что делать, если их 100001?

Вход. Первая строка содержит количество тестов t. Первая строка каждого теста содержит число студентов n (1 ≤ n ≤ 100001). Далее следуют n строк с описанием данных об обмене.

В каждой из этих строк указана информация об одном студенте: два целых числа, соответствующие текущему месту жительства студента и желаемому месту переезда. Места задаются неотрицательными целыми числами, не превышающими 10⁹. Ни у одного студента текущее место жительства не совпадает с желаемым.

Выход. Для каждого теста выведите в отдельной строке  “YES”,  если программу обмена можно успешно осуществить, и “NO” – в противном случае.

Пример входа	Пример выхода
2 6 1 2 100 200 1 2 2 1 200 100 2 1 4 1 2 15 16 17 18 19 20	YES NO

РЕШЕНИЕ

структуры данных - multiset

Анализ алгоритма

Для успешной реализации программы обмена необходимо, чтобы для каждого студента, желающего переехать из 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");

}