题解：P12748 [POI 2017 R2] 体育比赛 Sports competition

· · 题解

首先，可以构造出至少一种方案的充要条件是每一个排名都至少出现过一次，否则方案数是 0。

接着我们对于每个不确定名次的选手的 a_{i,1} 和a_{i,2} 之间连一条无向边，而确定排名就相当于给每条边分配一个相邻的点，可以发现所构成的图一定是由若干个基环树和链组成的，如果没有基环树，那么我们就可以确定唯一一种排名，可以证明每条链上一定有且仅有一个已经被固定排名的点，下图就是一种合法情况：

其中 3 号点已经被确定为一位选手的排名，为了确定其他选手的排名，我们可以从 3 号点开始枚举，将 2 号点分给 2 号边，4 号点分给 3 号边，以此类推。

如果无法确定唯一方案，最终方案数就是 2^k，其中 k 是基环树的个数，这是因为中间的环有两种分配方案。