题目：
小明陪小红去看钻石，他们从一堆钻石中随机抽取两颗并比较她们的重量。这些钻石的重量各不相同。在他们们比较了一段时间后，它们看中了两颗钻石g1和g2。现在请你根据之前比较的信息判断这两颗钻石的哪颗更重。
给定两颗钻石的编号g1,g2，编号从1开始，同时给定关系数组vector,其中元素为一些二元组，第一个元素为一次比较中较重的钻石的编号，第 二个元素为较轻的钻石的编号。最后给定之前的比较次数n。请返回这两颗钻石的关系，若g1更重返回1，g2更重返回-1，无法判断返回0。输入数据保证合 法，不会有矛盾情况出现。
测试样例：
2,3,[[1,2],[2,4],[1,3],[4,3]],4
返回: 1
1 #include <iostream> 2 #include <vector> 3 #include <string> 4 #include <queue> 5 #include <unordered_map> 6 #include <algorithm> 7 using namespace std; 8 9 /* 10 1>2 11 2>4 12 1>3 13 4>3 14 要判断2和3的关系 15 如果从2开始能遍历到3，那么2>3,反之2<3 16 类似图的广度优先遍历 17 1 建立一个哈希表，把左元素作为key，把右元素作为value（vector<int>结构） 18 2 以g1开始广度优先遍历，直到遍历到g2，则g1>g2；否则以g2开始广度优先遍历，直到遍历到g1，则g1<g2;否则条件不足无法判断 19 2.1 把与g1相连的顶点（即g1作为key对应的value）依次入队列 20 2.2 用一个哈希表标记遍历情况，key是顶点，value（bool类型）标记是否遍历过 21 */ 22 23 class Cmp { 24 bool compare(int g1, int g2, unordered_map<int, vector<int>> graph) 25 { 26 queue<int> que; 27 que.push(g1); 28 unordered_map<int, int> flag; 29 int temp; 30 while (!que.empty()) 31 { 32 temp = que.front(); 33 flag[temp] = 1; 34 que.pop(); 35 if (temp == g2) 36 return true; 37 else 38 { 39 for (int i = 0;i < graph[temp].size();i++) 40 { 41 if (!flag[graph[temp][i]])//如果graph[temp][i]没有被遍历过 42 que.push(graph[temp][i]); 43 } 44 } 45 } 46 return false; 47 } 48 public: 49 int cmp(int g1, int g2, vector<vector<int> > records, int n) { 50 // write code here 51 unordered_map<int, vector<int>> graph; 52 for (int i = 0;i < n;i++) 53 graph[records[i][0]].push_back(records[i][1]); 54 if (compare(g1, g2, graph)) 55 return 1; 56 else 57 { 58 if (compare(g2, g1, graph)) 59 return -1; 60 else 61 return 0; 62 } 63 } 64 }; 65 66 /* 67 测试样例： 68 2, 3, [[1, 2], [2, 4], [1, 3], [4, 3]], 4 69 返回: 1 70 */ 71 int main() 72 { 73 vector<vector<int> > v{ {1,2},{2,4},{1,3},{4,3} }; 74 Cmp solution; 75 cout<<solution.cmp(2,3,v,4); 76 return 0; 77 }