10763 – Foreign Exchange UVA Solution

This is an easy problem from uva judge http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1704

Data structures, STL MAP.

How I did it

• I read the pair numbers to read until I find a 0.
• I read all the pairs and save this into a map<int,int>.
• I traverse the map and check if the inverted key and value is equal to the key value. If this values are diferents I break the loop and set the answer as NO.Otherwise set the answer as YES.
• Print the answer.

Hints

•  The input is big 500000. So carefull if you want to use another brute force approach.

Code

#include <cstdio>
#include <map>
#include <algorithm>
using namespace std;

int main()
{
    map< pair<int,int>, int> myMap;
    int tot, from, to;
    pair<int,int> tmp;
    while(scanf("%d", &tot))
    {
        if(!tot)
           break;

        myMap.clear();

        for(int i=0; i<tot; i++)
        {
            scanf("%d %d", &from, &to);
            pair<int,int> p = make_pair(from, to);
            myMap[p]++;
        }

        bool flag = true;
        for(map< pair<int,int>, int>::iterator it=myMap.begin(); it!=myMap.end(); it++)
        {
            tmp = it->first;
            swap(tmp.first, tmp.second);
            if(myMap[tmp] != myMap[it->first])
            {
                flag = false;
                break;
            }
        }

        if(flag)
           printf("YES\n");
        else
            printf("NO\n");
    }
}