dc9*_*c95 6 algorithm graph-theory
在锦标赛图表中,我如何确定是否有一名球员主宰了所有其他球员？这种算法的运行时间是多少？
基本上,我需要找到是否有一个元素,我可以从中找到所有其他元素,遵循外链路径.
澄清:在这里; 如果'a'击败'b','b'击败'c',则a占据'c'.基本上,如果'a'直接或间接击败'c',它主导'c'."a"和"b"可能间接地相互支配,这就是胜利者可能存在或不存在的原因.也可能有不止一个赢家.
锦标赛图是有向图,其中每个元素具有与其余元素中的每个元素的有向边.所以有n*(n-1)/ 2个有向边,其中n是顶点(玩家)的数量.关于锦标赛图的维基百科文章
让我们T用N顶点和M边调用原始图。首先计算 的凝聚，T我们称之为G。每个顶点v的G代表的几个顶点T; 此外，您可以从该顶点中的任何一个到达T. 此外，G是一个 DAG。因此，如果 in 中只有一个顶点的入G度等于 0（我们称之为v0），这意味着您可以从 中的顶点开始到达原始图中的任何顶点v0。如果v0对应于 中的单个顶点T，那么它就是您正在寻找的顶点。复杂度是O(N+M)。