UVA 10763 (13.12.5)

Recommended for you: Get network issues from WhatsUp Gold. Not end users.

Problem E
Foreign Exchange
standard input
Output: standard output
Time Limit: 1 second

Your non-profit organization (iCORE - international Confederation ofRevolver Enthusiasts) coordinates a very successful foreignstudent exchange program. Over the last few years, demand has sky-rocketed andnow you need assistance with your task.

The program your organization runs works asfollows: All candidates are asked for their original location and the locationthey would like to go to. The program works out only if every student has asuitable exchange partner. In other words, if a student wants to go from A toB, there must be another student who wants to go from B to A. This was an easytask when there were only about 50 candidates, however now there are up to 500000 candidates!


The input file contains multiplecases. Each test case will consist of a line containing n - the numberof candidates (1≤n≤500000), followed by nlines representing the exchange information for each candidate. Each of theselines will contain 2 integers,separated by a single space, representing the candidate's original location andthe candidate's target location respectively. Locations will be represented bynonnegative integer numbers. You may assume that no candidate will have his orher original location being the same as his or her target location as thiswould fall into the domestic exchange program. The input is terminated by acase where n = 0;this case should not be processed.


For each testcase, print "YES" on asingle line if there is a way for the exchange program to work out, otherwiseprint "NO".

SampleInput Output for Sample Input


1 2

2 1

3 4

4 3

100 200

200 100

57 2

2 57

1 2

2 1


1 2

3 4

5 6

7 8

9 10

11 12

13 14

15 16

17 18

19 20





Problem setter: Gilbert Lee, University of Alberta,Canada

D: is that if there is a 12 number on the number 21, so there must be a corresponding to the~

Methods: two arrays, each array. Each of the first and second numbers, and then sort

But the Internet has the solution of the problem, see bug, such as three to the array, 12, 23, 31, according to the problem is not with me, but this method is YES...

AC code:


using namespace std;

int num1[555555];
int num2[555555];

int main() {
    int n;
    while(scanf("%d", &n) != EOF && n) {
        for(int i = 0; i <n; i++)
            scanf("%d %d", &num1[i], &num2[i]);
        sort(num1, num1+n);
        sort(num2, num2+n);

        int mark = 1;
        for(int i = 0; i <n; i++) {
            if(num1[i] != num2[i]) {
                mark = 0;
    return 0;

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download

Posted by Michell at December 10, 2013 - 4:24 AM