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

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

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

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

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

Пример входа	Пример выхода
2 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	YES NO

РЕШЕНИЕ

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

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

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

Пример

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

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

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

multiset<pair<int,int> > s;

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

Читаем количество тестов t.

scanf("%d",&t);

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

while(t--)

{

scanf("%d",&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");

}

Java реализация

Object – корень иерархии классов. Каждый класс имеет Object как суперкласс. Аннотация @Override информирует компилятор о том, что метод перегружает метод в суперклассе.

import java.util.*;

public class Main

{

static class Pair

{

int First, Second;

Pair(int First, int Second)

{

this.First = First;

this.Second = Second;

}

@Override

public int hashCode()

{

final int prime = 33533;

int result = 1;

result = prime * result + First;

result = prime * result + Second;

return result;

}

@Override

public boolean equals(Object obj)

{

Pair other = (Pair) obj;

if (First != other.First) return false;

if (Second != other.Second) return false;

return true;

}

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int tests = con.nextInt();

while(tests-- > 0)

{

HashMap<Pair, Integer> Hash = new HashMap<Pair, Integer>();

int n = con.nextInt();

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

{

int a = con.nextInt(), b = con.nextInt();

Pair ReversePair = new Pair(b,a);

if (Hash.containsKey(ReversePair))

{

if (Hash.get(ReversePair) > 1)

Hash.put(ReversePair, Hash.get(ReversePair) - 1);

else Hash.remove(ReversePair);

} else

{

Pair p = new Pair(a,b);

if (Hash.containsKey(p))

Hash.put(p, Hash.get(p) + 1);

else Hash.put(p, 1);

}

}

System.out.println(Hash.isEmpty() ? "YES" : "NO");

}

}

}