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

Следует написать программу для обмена иностранными студентами. Каждый студент желает переехать из некоторого города А в город В. Программа сработает, если у каждого студента будет партнер для обмена. То есть если некоторый студент желает переехать из А в В, то должен существовать студент, желающий переехать из В в А. Выяснить, можно ли выполнить программу по обмену студентов, если известны все их желания по перемещению.

Вход. Состоит из нескольких тестов. Первая строка каждого теста содержит количество студентов для обмена n (1 £ n £ 500000). Каждая из следующих n строк содержит номер города А, откуда студент желает выехать и номер города В, куда он хочет приехать. Последний тест содержит n = 0 и не обрабатывается.

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

Пример входа

10

1 2

2 1

3 4

4 3

100 200

200 100

57 2

2 57

1 2

2 1

10

1 2

3 4

5 6

7 8

9 10

11 12

13 14

15 16

17 18

19 20

0

Пример выхода

YES

NO

РЕШЕНИЕ

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

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

В задаче достаточно для каждой пары (А, В) поставить в соответствие пару (В, А). Входные пары могут повторяться. Для хранения данных будем использовать мультимножество. Для каждой входной пары (А, В) будем искать в мультимножестве пару (B, A). Если таковая имеется, то удалим ее. Иначе внесем в мультимножество пару (А, В). Если в конце обработки данных мультимножество будет пустым, то это будет означать что для каждой пары (А, В) была найдена пара (В, А), и программу обмена студентами можно выполнить.

Пример

В первом тесте для каждой пары (A, B) найдется соответствующая пара (B, A). Во втором тесте ни одно желание студента не может быть выполнено.

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

Заведем мультимножество пар s. В процессе работы в нем будут храниться лишь такие пары (А, В), для которых нет соответствующей пары (В, А).

multiset<pair<int,int> > s;

multiset<pair<int,int> >::iterator iter;

После чтения количества студентов n очищаем мультимножество s. Для каждой входной пары (А, В) проверяем, есть ли в мультимножестве пара (В, А). Если есть – то удаляем (В, А), иначе – вставляем (А, В).

while(scanf("%d",&n),n)

{

s.clear();

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

{

scanf("%d %d",&a,&b);

if ((iter = s.find(make_pair(b,a))) == s.end()) s.insert(make_pair(a,b));

else s.erase(iter);

}

Если в конце работы мультимножество s пусто, то у каждой пары (А, В) существует соответствующая ей пара (В, А) и обмен студентами может быть успешно произведен.

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

else printf("NO\n");

}