图表示的算法问题

Question

假设我有N支足球队。对于每一支球队，我都知道哪些对手可以击败她(对手的排名可能是0)。如果我能“修正”比赛(自己安排)，我需要看看有多少支球队我可以修正一个胜利的结果。

例如，假设我有5支球队。输入：

5
1 5 (team 1 loses from 1 opponent->5)
3 1 4 5(team 2 loses from 3 opponents->1,4,5)
2 1 4(team 3 loses from 2 opponents->1,4)
1 1
1 3

输出:4(我可以修正1，3，4，5的结果)，如果我想，例如，1赢，比赛必须：

1. 5-3 => winner=3
2. 4-1 => winner=1
3. 3-1 => winner=1
4. 2-1 => winner=1

我想要创建一个有向图，其中边(u，v)从u到v意味着u队输掉了V队。如果比赛是在决赛队v(假设我们想要v赢)必须与属于u到v顶点(u输v)的球队比赛。所以U队要么直接跳到决赛，要么打一场决赛前的比赛，用同样的逻辑赢得比赛。我想问的是:当有多个(u，v)边(v是我们想要赢的球队)时，我们该怎么办？在找到一支输给v的球队后，我被困住了，不知道怎么继续。

Answer 1

单淘汰赛的输家树是一棵树，其中胜利者是根，而对方节点的父节点是它失去的节点。正如Prune所指出的，您可以修复特定节点的锦标赛当且仅当有一个输家树，其中该节点是根，每个输家->胜利者弧出现在图表中。“只有当且仅当”方向是明显的；"if“方向是通过按后续顺序遍历的顺序来安排匹配。

将此逻辑进一步发展一步，存在这样的树当且仅当有一个有向路径从赢家到对方节点。“只有当”方向是明显的(只提取树中的路径)；"if“方向跟随，如Prune指出的，从深度优先或广度优先搜索。

用强连通分量对图的可达性结构进行了总结。Tarjan给出了一个线性时间算法来标记每个节点的强连通分量.考虑到这些标签，您需要的正是一个强连接的组件，其中没有节点与任何其他组件具有传出弧。这个组件中的每个人都可以成为赢家，而没有其他人可以。如果有两个或更多这样的组成部分，那么(a)我想抽签一场比赛是可能的(b)没有可能的赢家。