钻石重量比较算法：判断两个编号的钻石重量关系

"该资源是网易2016年暑期实习生研发工程师笔试题，主要涉及的问题是一个基于比较的排序问题，要求根据比较记录来确定两颗特定钻石的重量关系。" 在题目中，小明和小红对一堆不同重量的钻石进行了比较，每颗钻石有一个唯一的编号。他们通过一系列的比较，确定了某些钻石之间的重量关系。给定的输入包括两颗钻石g1和g2的编号，一个表示比较结果的关系数组vector，以及总的比较次数n。关系数组中的每个元素是一个二元组，表示在一次比较中哪颗钻石更重。题目保证输入数据不会出现矛盾。 任务是根据这些信息判断g1和g2哪颗钻石更重，返回值为1表示g1更重，-1表示g2更重，0表示无法判断。为了实现这个功能，可以采用以下策略： 1. **构建关系图**：首先，我们需要从关系数组中构建一个有向图，其中每个节点代表一颗钻石，边的方向表示重量关系，从较重的钻石指向较轻的钻石。这个有向图实际上形成了一个森林结构，因为可能存在多个没有关联的子树。 2. **层次遍历**：题目中提到可以采用层序遍历的方式来解决这个问题。对于每棵树（即森林中的一个子树），我们可以分别从g1和g2开始进行层次遍历。如果在以g1为根的树中找到g2，或者在以g2为根的树中找到g1，那么就可以确定两者的重量关系。 3. **实现细节**：在提供的代码片段中，定义了一个名为`Cmp`的类，包含一个内部函数`judge`用于判断g1是否比g2重，以及一个公共函数`cmp`作为主入口，接收g1、g2、比较记录和比较次数作为参数。`cmp`函数首先将比较记录转换为一个映射，然后调用`judge`进行判断。`judge`函数使用队列进行层次遍历，标记已访问的节点，并在找到目标节点时返回结果。 4. **优化与效率**：由于题目保证了输入数据的合法性，所以可以避免出现死循环或无法判断的情况。层次遍历的方法可以有效地遍历整个森林，确保在有限次比较后找出答案。此外，使用`unordered_map`存储和查询关系可以提供快速的常数时间复杂度，提高算法效率。 这道笔试题考察了数据结构（如有向图、森林）、图遍历（层次遍历）以及问题解决能力。通过理解题目中的关系和提供的代码，可以深入学习到如何利用图来表示和解决问题，以及如何有效地遍历和搜索图结构。