图论：在锦标赛图中寻找获胜者的算法（如果有的话）
Graph-Theory: Algorithm to Find Winner in Tournament Graph (if there is any)
在锦标赛图表中，如何找到是否有一个玩家统治了所有其他玩家？这种算法的 运行 时间是多少？
基本上，我需要找到是否有一个元素，从中我可以沿着外链路径到达所有其他元素。
澄清：这里；如果 'a' 打败 'b'，并且 'b' 打败 'c'，则 a 支配了 'c'。基本上，如果 'a' 直接或间接击败 'c'，它就统治了 'c'。 'a' 和 'b' 可能间接地相互支配，这就是为什么赢家可能存在也可能不存在的原因。获奖者也可能不止一位。
锦标赛图是一个有向图，其中每个元素与其余元素中的每一个都有一条有向边。所以有 n*(n-1)/2 条有向边，其中 n 是顶点（玩家）的数量。 Wikipedia article on Tournament Graph
一种方法是获取每个顶点，并以该顶点为根深度搜索图形。对于每次深度搜索，您都会检查您是否访问过所有其他顶点。如果有，则对应于该顶点的玩家支配图中的所有玩家。如果你熟悉 C++，我可以在这里编写程序。时间复杂度是~O(N^3)。您需要更快的算法吗？ N 是顶点数
如果有一个玩家统治了其他所有人，那么图中只存在一个顶点 v 没有入边。从v开始做一个DFS。如果你能到达所有其他顶点，那么v就是主导顶点。
编辑 1：正如 kaktusito 所建议的，我们可以在应用 DFS 之前压缩图形。
编辑 2：看起来没有必要显式计算所有连接的组件、应用压缩、构建 DAG 并找到主导顶点。相反，这里有一个更简单的解决方案：
首先对图进行DFS，找到完成时间最长的节点v。如果图中有赢家，则 v 必须在其中。否则会有另一个顶点 u 使得 v 可以从 u 到达并且具有较晚的完成时间。现在要找到其他获胜者，使用来自 v 的 DFS 或 BFS，在转置图中找到从 v 可达的所有节点。该算法的复杂度仍然是 O(V+E)，但实现（和常量）是简单得多。
让我们用 N 个顶点和 M 个边调用原始图 T。首先计算 T 的缩合，我们称它为 G。 G的每个顶点v代表T的几个顶点；此外，您可以从任何一个顶点到达 T 中的另一个顶点。此外，G 是一个 DAG。因此，如果 G 中只有一个入度等于 0 的顶点（我们称之为 v0），这意味着您可以从 [= 中的一个顶点开始到达原始图中的任何顶点21=]。如果 v0 对应于 T 中的单个顶点，那么它就是您正在寻找的顶点。复杂度是O(N+M).
在锦标赛图表中，如何找到是否有一个玩家统治了所有其他玩家？这种算法的 运行 时间是多少？
基本上，我需要找到是否有一个元素，从中我可以沿着外链路径到达所有其他元素。
澄清：这里；如果 'a' 打败 'b'，并且 'b' 打败 'c'，则 a 支配了 'c'。基本上，如果 'a' 直接或间接击败 'c'，它就统治了 'c'。 'a' 和 'b' 可能间接地相互支配，这就是为什么赢家可能存在也可能不存在的原因。获奖者也可能不止一位。
锦标赛图是一个有向图，其中每个元素与其余元素中的每一个都有一条有向边。所以有 n*(n-1)/2 条有向边，其中 n 是顶点（玩家）的数量。 Wikipedia article on Tournament Graph
一种方法是获取每个顶点，并以该顶点为根深度搜索图形。对于每次深度搜索，您都会检查您是否访问过所有其他顶点。如果有，则对应于该顶点的玩家支配图中的所有玩家。如果你熟悉 C++，我可以在这里编写程序。时间复杂度是~O(N^3)。您需要更快的算法吗？ N 是顶点数
如果有一个玩家统治了其他所有人，那么图中只存在一个顶点 v 没有入边。从v开始做一个DFS。如果你能到达所有其他顶点，那么v就是主导顶点。
编辑 1：正如 kaktusito 所建议的，我们可以在应用 DFS 之前压缩图形。
编辑 2：看起来没有必要显式计算所有连接的组件、应用压缩、构建 DAG 并找到主导顶点。相反，这里有一个更简单的解决方案：
首先对图进行DFS，找到完成时间最长的节点v。如果图中有赢家，则 v 必须在其中。否则会有另一个顶点 u 使得 v 可以从 u 到达并且具有较晚的完成时间。现在要找到其他获胜者，使用来自 v 的 DFS 或 BFS，在转置图中找到从 v 可达的所有节点。该算法的复杂度仍然是 O(V+E)，但实现（和常量）是简单得多。
让我们用 N 个顶点和 M 个边调用原始图 T。首先计算 T 的缩合，我们称它为 G。 G的每个顶点v代表T的几个顶点；此外，您可以从任何一个顶点到达 T 中的另一个顶点。此外，G 是一个 DAG。因此，如果 G 中只有一个入度等于 0 的顶点（我们称之为 v0），这意味着您可以从 [= 中的一个顶点开始到达原始图中的任何顶点21=]。如果 v0 对应于 T 中的单个顶点，那么它就是您正在寻找的顶点。复杂度是O(N+M).