UVA 10763

火冰狐

　　连接：戳我。AC了。
　　这道题可以有两种解法：
　　思路一：用一个 Adjancency Matrix： Edge[][] 来储存 u->v 的数目：
　　每当遇到 u->v：Edge[v]++ & Edge[v]--。
　　最后检索一下整个 matrix，如果都为0，那么就是YES，否则为NO。
　　
　　思路二：把每个 src->dest 用一个 Node 来储存，用一个 array 来储存这些 Node。
　　首先：按照起始点的大小来排序；
　　接着：通过用lower_bound & upper_bound 找到 src->dest & dest->src 的所有 Node 的数量。
　　如果不同则返回，否则就继续找。
　　



1 /*
2   Author: frankdj
3   State:  AC
4 */
5 #include <iostream>
6 #include <vector>
7 #include <algorithm>
8 #include <cstring>
9 using namespace std;
10
11 const int kMaxNodeNum = 500003;
12
13 struct Node {
14     int src;
15     int dest;
16 };
17
18 bool Compare(Node a, Node b) {
19     if (a.src < b.src) {
20         return true;
21     } else if (a.src > b.src) {
22         return false;
23     } else {
24         return a.dest < b.dest;
25     }
26 }
27
28 bool Check(vector<Node> candidates, int used[]) {
29     vector<Node>::iterator iterator = candidates.begin(),
30         lower_from, upper_from, lower_back, upper_back;
31     while (iterator != candidates.end()) {
32         Node from = *(iterator);
33         Node back;
34         back.src = from.dest;
35         back.dest = from.src;
36
37         lower_from = lower_bound(candidates.begin(), candidates.end(), from, Compare);
38         upper_from = upper_bound(candidates.begin(), candidates.end(), from, Compare);
39
40         lower_back = lower_bound(candidates.begin(), candidates.end(), back, Compare);
41         upper_back = upper_bound(candidates.begin(), candidates.end(), back, Compare);
42
43         int from_range = (upper_from - candidates.begin()) -
44             (lower_from - candidates.begin());
45         int back_range = (upper_back - candidates.begin()) -
46             (lower_back - candidates.begin());
47
48         if (from_range != back_range) {
49             return false;
50         } else {
51             iterator = upper_from;
52         }
53     }
54     return true;
55 }
56
57
58 int main(int argc, char *argv[]) {
59 #ifndef ONLINE_JUDGE
60     freopen("input.txt", "r", stdin);
61 #endif
62
63     int candidates_count = 0;
64     vector<Node> candidates;
65     int used[kMaxNodeNum];
66
67     while (cin >> candidates_count && candidates_count != 0) {
68         memset(used, 0, sizeof(used));
69         candidates.erase(candidates.begin(), candidates.end());
70
71         for (int i = 0; i < candidates_count; i++) {
72             Node candidate;
73             cin >> candidate.src >> candidate.dest;
74             candidates.push_back(candidate);
75         }
76
77         sort(candidates.begin(), candidates.end(), Compare);
78
79         if (Check(candidates, used)) {
80             cout << "YES" << endl;
81         } else {
82             cout << "NO" << endl;
83         }
84     }
85     return 0;
86 }