1226. Foreign
Exchange
Your non-profit
organization coordinates a student exchange program and needs your help.
The exchange
program works as follows: each participant specifies their current place of
residence and the place to which they would like to move. The program is
considered successful if a suitable exchange partner can be found for every
student. In other words, if a student wants to move from A to B, there must
exist another student who wants to move from B to A.
Such a check is
easy to perform when there are only participants, but what should be
done if there are 100001?
Input. The first line
contains the number of test cases t. The first line
of each test case contains the number of students n (1 ≤ n ≤ 100001). This is followed by n lines describing the exchange
data.
Each of these
lines contains information about one student: two integers representing the
student’s current place
of residence and the desired destination. Locations are given as non-negative
integers not exceeding 109. The current and desired locations are
different for every student.
Output. For each test case, print “YES” on a separate line if the
exchange program can be carried out successfully, and “NO” otherwise.
|
Sample
input |
Sample
output |
|
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 |
data
structures - multiset
For the exchange program to be successfully implemented, every student
who wants to move from A to B must have another student who wants to move from
B to A. In other words, each pair (A, B) must have a corresponding reverse pair
(B, A). Identical pairs may appear multiple times.
We’ll use a multiset to store the pairs. The algorithm works as follows:
·
For each input
pair (A, B), check whether the pair (B, A) is present in the multiset.
·
If such a pair is
found, remove it from the multiset, thereby forming a valid exchange pair.
·
If the reverse
pair does not exist, add the current pair (A, B) to the multiset.
After processing all the students, there are two possible cases:
·
The multiset is
empty
– this means that for every pair (A, B),
a corresponding reverse pair (B, A) was found, and the exchange program can be
successfully carried out.
·
The multiset is
not empty – this means that some students
do not have a suitable partner, and the exchange program cannot be completed.
Based on this, the output is either “YES” or “NO”.
In the first test, every
pair (A, B) has a corresponding reverse pair (B, A). In the second test, none
of the students’ requests can be fulfilled.
Algorithm implementation
Declare a multiset of
pairs s. During execution, it will store only those pairs (A, B) for
which a corresponding reverse pair (B, A) has not yet been found.
multiset<pair<int,int> > s;
Read the number of test
cases t.
scanf("%d",&t);
Process the t test
cases sequentially.
while (t--)
{
Read the number of students n.
scanf("%d", &n);
Before processing each test case, clear the multiset.
s.clear();
Process the students’ requests sequentially.
for (i = 0; i < n; i++)
{
Read the pair (a, b) and look for a student with the
opposite exchange direction.
scanf("%d %d", &a, &b);
auto it = s.find({ b, a });
If the reverse pair is not found, the current pair (a, b) is
added to the multiset s.
If the reverse pair is found, it is removed from s, since a partner
for this exchange has been found.
Thus, s always contains only those pairs for which a match has not
yet been found.
if (it == s.end()) s.insert({ a, b });
else s.erase(it);
}
If, after processing all students, the multiset is empty, it means that a
reverse pair was found for every pair, and the exchange program can be
successfully carried out. Otherwise, print “NO”.
if (s.empty()) printf("YES\n");
else printf("NO\n");
}