我一直在研究解决这个问题的算法，但没能搞清楚问题如下：
有N支球队参加比赛。每场比赛结束后，失败者将被从锦标赛中除名，胜利者将继续比赛而无需参加下一场比赛。两队一次比赛，直到只剩下一队获胜。
我们在集合e中也得到了一些成对的团队，这样成对的团队就意味着团队将击败团队。集合中的配对不包括所有可能的比赛，也不具有传递性（team(i,j)beats teami，teamjbeats teamE并不意味着teamibeats teamj）
我们需要找到一个j时间算法来计算一组球队k，这样对于每个球队i在k中，存在一个可能的时间表，其中球队O(n + |E|)保证赢得比赛。
最佳答案
看起来像是Tarajan's strongly connected components alghorithm任务。
假设团队的集合是V并且如果定向边的集合是E。方向与获胜队伍相对应。
如果该组件中的每个顶点都可以从该组件的其他顶点访问，则该组件是强连接的这意味着该组件中的每个团队都可以在该组件中的其他团队中获胜，因为您可以根据需要安排游戏。因此，来自这样一个组件的每个团队要么在a中，要么两者都不在a中，所以您可以将每个这样的组件看作一个单独的“大团队”。该算法会找到所有这样的组件，因此最终会得到一个没有强连接组件的“大型团队”的有向图，因此对该图有一个顺序。
现在你把所有没有父母的“大团队”都带走。这意味着没有人能保证打败这支大球队。我们把这个集合称为“最强的团队”（这也是原始图的强连接组件集合）。这可以在线性时间内完成，因为您只需遍历图形现在，如果“最强的球队”有一个以上的“大球队”，那么你不能保证赢家。否则它只有一个“大团队”，那就是你的A组。
注意Tarajan's strongly connected components alghorithm运行为O(|V| + |E|)，所以在您的例子中，它是O(n + |E|)并且遍历“大型团队”图是O(n)所以这就是您如何使用O(n + |E|)找到a的方法。
关于algorithm - 算法计算一组保证会赢得比赛的球队，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/32752828/