@ninijia 在 Leetcode每日一题练习 ------ 2924. 找到冠军 II 中发帖
从Leetcode 每日一题练习继续讨论:
2924. 找到冠军 II
2924. Find Champion II
题解
本题使用简化版拓扑排序可以解决,拓扑排序在以前的题目中曾经讲解过,在有向无环图中,拓扑排序表示的是一种抽象的先后关系,如若节点均表示数字,则这种先后关系就可以是数字之间的相对大小,若把节点看成一个个在排队的人,则这种先后关系可以是一个人排在另一个人的前面。这种抽象的关系可以对应到各种实际情况中。对于本题,一条有向边相当于一支队伍打赢了另外一支队伍,那么拓扑排序的起始队伍就相当于打赢了其他队伍但没人打赢它,如果这样的队伍只有一个,显然就是冠军,不止有一个那说明还需要更多比赛。
之所以说是简化的拓扑排序,在于本题理解题面可以用拓扑排序的思想,但实际解题,只需要记录下所有节点(队伍)的入度(即有几支队伍打赢了它),最终找到所有入度为0的队伍,只有一个直接返回,否则返...