集训队作业yuan tournamentpoi xi oi stage ii解题报告

1、2005年信息学国家集训队作业 安徽 周源Tournament（POI XI OI Stage II）解题报告安徽 周源摘要算法连通分量+寻找基源寻找特殊点+扩展强连通分量时间复杂度O(n + m)O(n + m)空间复杂度O(n + m)O(n + m)问题简述国际X-Game联盟组织了一次锦标赛，有n个程序即将参赛，它们被编号为1至n。本次比赛的规则如下：如果比赛中还剩下多于一个参赛的程序，那么随机选择两个不同的程序进行一场比赛。失败方（X-Game中没有平局）就被淘汰出局，重复这一过程(n-1)次直到只剩一个程序为止，而这个程序就是本次比赛的获胜者。我们有一些以前比赛的结果可以作为参考。

2、显然，每个程序的走法都是确定的，即任意两个程序无论何时何地比赛，胜者一定是唯一的。所以如果双方对阵的情况在以前的比赛中出现过，那么本次比赛的胜者将和以前一样。然而如果两者以前没有比过，则这次对阵的结果无法被预测：两个程序都有获胜的可能性。而我们希望得到所有的可能最终获胜的程序编号。数据规模：n不大于100,000，可供参考的比赛盘数不超过1,000,000。分析不妨构造这样一张描述比赛的图：设每一个参赛程序都是图中的一个点，如果点i从前可以赢点j，则从i向j连一条有向边。而若i和j在先前没有打过比赛，则从i向j，以及从j向i分别连一条有向边，表示它们都有胜对方的可能。这样问题就显得很清楚了：如

3、果一个程序i有最终获胜的可能，那么其对应的点i一定可以通过有向边到达所有的其他点，即它可以直接或是间接的打赢每一个对手。这也就转化成为求有向图的基源问题了。所谓基源，即求出有向图的每一个强连同分量，保留强连同分量之间的边，可以看出这是一幅新的有向图无环图，而没有入度的强连同分量则是我们要求的基源。在本题中，显然基源只有一个，基源中的点可以到达其它的所有的点，而非基源中的点一定不可能到达基源中的点，据此最终可能获胜的点集就是我们求得的基源。而时间复杂度的问题随之而来：求强连同分量以及基源的复杂度是O(N + M)，其中N为点数，M为边数。而在我们新构造的图中，任意两个点之间都有边相连（有的还不止

4、一条边），因此新图中的M是O(n2)的级别，无论是时间还是空间都无法让我们接受。而事实上，过多的边数主要是我们构造而来，而我们的构造又是十分有规律的。事实上，我们每次添加一定都是2条有向边，而就连通性来说，这两条边完全可以被一条无向边所替代。也就是说，在新构造的图中，原图的m条有向边保留，而又添加了约O(n2)条无向边。如果在这个新图上求强连通分量，可以先求无向边构成的无向图的连通分量，接着问题就迎刃而解了。如何求无向边的连通分量呢？这个问题等价于：给出一个无向图，有m条边，需要求出这个图的补图的连通分量。使用一个巧妙的扫描算法，可以做到O(n + m)的时间复杂度。我们使用邻接表存储这个图：

5、每个节点后链接了一个有序（从小到大）的链表，表示图中与这个点相连接的节点。我们算法的输入是一个有序集合/数列S，以及一个节点p，表示要在S引导出的子图的补图中，找出与p连通的点。使用宽度优先搜索的方法：初始时队列中仅有一个点p，而令S = S / p，表示要在剩余的集合中寻找与p连通的点。接着，取出队列中的一个点p，设其邻接表为T，那么S / T这个集合中的点显然与p是连通的，而且由于S表示的是剩余的未处理的点，因此这些节点都将被加入队列中，同时让S = S T：这些是在一轮处理后剩余的点。而问题的重点就在于，在|S| + |T|次操作内，完成这次扫描过程。由于S和T都是有序的，设两个指针i和

6、j分别指向它们的第一个元素。如果Si = Tj，则说明这个元素属于S T，将其放入新的S中，i和j指针同时加1；如果Si Tj，则将j指针加1即可。在我们找连通分量的算法中，初始时S即为全部点的集合，先将p = 1代入过程执行，就可以得到和1连通的点，而此时S则是剩余的和1不连通的点集，任意选择S中的一个元素继续执行即可得到所有的连通分量。下面来分析一下这个算法的时间复杂度，算法最多进行n次扫描操作：即对每个点的邻接表和当时的S进行一次扫描。而每次的扫描复杂度为邻接表和当时S大小之和。全部邻接表之和为m，因此扫描操作中所有含有j指针加1的操作都可以平摊入这一部分。那么只有第二条操作“如果Si

7、Tj”的复杂度需要另行计算，而此时，Si点将被归入S / T一部分以后不会再被处理到，因此这一部分的总复杂度为O(n)。综上所述，整个算法的时间复杂度为O(n + m)。而找到连通分量之后，在连通分量之中寻找基源的复杂度也仅为O(m)，因此可以在O(n + m)的时间内解决本题。至此，本题已经得到了解决。然而，汪汀同学根据本题的特殊性，提出了一个更加简便的方法。本题与求一般图的基源最大的不同就是：本题的基源只有一个！因此我们可以任意寻找一个基源中的点，在此基础上扩展出一个强连通分量即可。如何寻找一个需要的点呢？注意本题的题目描述，我们只需要任意确定一种比赛方案，那么这个方案的胜者一定是满足条件的，也就是基源中的点：比如我们可以让1号和2号对打，胜者和3号对打，胜者再和4号对打这样重复(n-1)次就可以了。而这一步完全可以在O(nlogm)的时间内完成（因为要二分寻找边）。