我们先看解题步骤:
1.建塔:以每个未出现过的点为顶点建立金字塔。
1.1.测环:建立过程中每个查询到的节点都记录到一个数组,如果出现重复,即有环。
1.2保存被依赖:记录每个元素被依赖的元素。
2.去重:如果元素在金字塔底层出现,就不能在上层出现,即向上去重(被依赖的元素永远在依赖元素的上层)。
3.合并:所有金字塔根据共同元素进行合并(从上层开始遍历查找第一个共同元素)并去重。
4.定位:经过以上步骤,所有金字塔或两两之间(现在顶端可能有很多个元素,应该叫做每一栋楼)没有重复元素。找到每个元素所在的金字塔,以及所在层,与1.2中记录的被依赖元素一起保存。
经过以上步骤,所有元素在对应塔里面有了它对应的层级,以及上层依赖它的元素,无论从哪一层哪一个元素开始都可以往上找到所有依赖关系。
再看解题思路
目的:理清各个元素之间的依赖关系
解题思路:即是依赖关系,便有层级结构,以公司结构为例,普工,主管,秘书,老板,,普工依赖主管和老板,主管依赖老板,秘书依赖老板,秘书依赖主管。。。。但老板不能依赖普工,秘书不能依赖普工,否则会形成环。 这个例子当中层级关系是普工,秘书,主管,老板。 由于秘书依赖主管,所以秘书层级在主管下面,而不是老板下面(例子不合理现实别计较)。
建模:由思路得出可以用等级来解决,以大厦为模型,楼层就是级别,把所有人按分好层级,即如果有人级别高,那他依赖的人必然级别低于他,如果他被低级别的人依赖了,那他的级别必须降到低级别的人下面去。
行为方式:每个人身上都记录了自己所在的楼以及楼层,以及依赖他的人的id,也就是找到这个人就可以找到他所有依赖他的人。