uva 10763 多种方法

题意：给出n个二元组，让你判断是否每一个二元组都存在一个与之对应的对称的二元组，且每个二元组不能和多个其他二元组相对应。

方法1：

利用map来为每个二元组计数，判断是否有map[a][b] == map[b][a]。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <map>
 4 using namespace std;
 5 
 6 typedef pair<int, int> pii;
 7 map<pii, int> mp;
 8 map<pii, int>::iterator it;
 9 
10 int main ()
11 {
12     int n;
13     while ( scanf("%d", &n), n )
14     {
15         mp.clear();
16         for ( int i = 0; i < n; i++ )
17         {
18             int a, b;
19             scanf("%d%d", &a, &b);
20             mp[make_pair( a, b )]++;
21         }
22         bool flag = true;
23         for ( it = mp.begin(); it != mp.end(); it++ )
24         {
25             int a = (*it).first.first, b = (*it).first.second;
26             pii p1 = make_pair( a, b ), p2 = make_pair( b, a );
27             if ( mp[p1] == mp[p2] )
28             {
29                 mp.erase(p1);
30                 mp.erase(p2);
31             }
32             else
33             {
34                 flag = false;
35                 break;
36             }
37         }
38         if ( flag ) printf("YES
");
39         else printf("NO
");
40     }
41     return 0;
42 }

方法2：

也是利用了map，不过看起来更加巧妙，见代码。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <map>
 4 using namespace std;
 5 
 6 typedef pair<int, int> pii;
 7 map<pii, int> mp;
 8 map<pii, int>::iterator it;
 9 
10 int main ()
11 {
12     int n;
13     while ( scanf("%d", &n), n )
14     {
15         mp.clear();
16         for ( int i = 0; i < n; i++ )
17         {
18             int a, b;
19             scanf("%d%d", &a, &b);
20             mp[make_pair( a, b )]++;
21             mp[make_pair( b, a )]--;
22         }
23         bool flag = true;
24         for ( it = mp.begin(); it != mp.end(); it++ )
25         {
26             if ( (*it).second != 0 )
27             {
28                 flag = false;
29                 break;
30             }
31         }
32         if ( flag ) printf("YES
");
33         else printf("NO
");
34     }
35     return 0;
36 }

方法3：

对所有的二元组按照first排序，再按照second排序，观察结果是否一样。

 1 #include <algorithm>
 2 #include <cstdio>
 3 using namespace std;
 4 
 5 const int N = 500000;
 6 
 7 struct Node
 8 {
 9     int first;
10     int second;
11 } node1[N], node2[N];
12 
13 bool cmp1( Node x, Node y )
14 {
15     if ( x.first != y.first )
16         return x.first < y.first;
17     return x.second < y.second;
18 }
19 
20 bool cmp2( Node x, Node y )
21 {
22     if ( x.second != y.second )
23         return x.second < y.second;
24     return x.first < y.first;
25 }
26 
27 int main ()
28 {
29     int n;
30     while ( scanf("%d", &n), n )
31     {
32         for ( int i = 0; i < n; i++ )
33         {
34             int a, b;
35             scanf("%d%d", &a, &b);
36             node1[i].first = a, node1[i].second = b;
37             node2[i].first = a, node2[i].second = b;
38         }
39         sort( node1, node1 + n, cmp1 );
40         sort( node2, node2 + n, cmp2 );
41         bool flag = true;
42         for ( int i = 0; i < n; i++ )
43         {
44             if ( node1[i].first != node2[i].second
45               || node1[i].second != node2[i].first )
46             {
47                 flag = false;
48                 break;
49             }
50         }
51         if ( flag ) printf("YES
");
52         else printf("NO
");
53     }
54     return 0;
55 }