UVA 10763
连接：戳我。AC了。这道题可以有两种解法：
思路一：用一个 Adjancency Matrix： Edge[][] 来储存 u->v 的数目：
每当遇到 u->v：Edge++ & Edge--。
最后检索一下整个 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;
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 }
页:
[1]