竞赛图是有向完全图，我见到的题包括给定一个竞赛图或者是竞赛图的计数问题。

首先给出两个结论：

1>：任意竞赛图都有哈密顿路径（经过每个点一次的路径，不要求回到出发点）。

2>：竞赛图存在哈密顿回路的充要条件是强联通。

显然如果我们可以证明出结论2的话，对于一般竞赛图的哈密顿路径我们只需tarjan按照拓扑顺序得到。

结论2证明：

用归纳法，显然对于n=1,2的情况是满足结论的，那么我们证明n>=3时只需要由1-n-1都满足这个性质来推即可。

1>：

若在原n-1个点构成的强联通的竞赛图中新添加的一个点。

原图一定存在一个哈密顿回路，并且第n个点与前n-1个点之间的边一定不是同向的（满足一个强联通分量）。

所以将环上的点依次排列，一定存在一个点p，使得存在边p->n&&n->nxt[p]或n->p&&nxt[p]->n。

这样就可以直接把n加进去了。

2>：

若原n-1个点不是一个强联通分量。

按照拓扑序，找到head，tail。n一定存在tail中一个点p存在边p->n，同理head中一定有一个点p存在边n->p。

这样就直接将哈密顿链首位连接了。

哈密顿路径构造：

首先记录当前链的head，tail。

依次枚举剩下的点加入。

1>：x->head，直接把head改成x。

2>：tail->x，直接把tail改成x。

3>：否则，一定存在head->x，x->tail。即一定存在一个点p使得p->x，x->nxt[p]。

通过哈密顿路径构造哈密顿回路：

首先找到一个最靠右的点p，满足p->head。

然后就从p之后点的开始加入环内。

我们考虑会存在一种情况是现在环上所有点都指向p，那么p肯定是通过之后的一个点连接到环内。

所以我们记录一个pre代表插入的链的左端点，当p满足到环上某个点时，就把[pre,p]这个链插入到环中。

因为[pre,p)与环上的点之间的边都是指向自己的，所以一定存在环上一个点x满足x->pre&&p->nxt[x]，然后插入即可。

计数题：

bzoj 5219

codeforces 913 F Strongly Connected Tournament

codeforces 804 F Fake bullions （神仙题）

hdu 5503 EarthCup：

题目描述：给定每个点的获胜次数，问是否存在这样的竞赛图。

显然会想到一个网络流做法，左边n*(n-1)/2个点，右边n个点跑最大流即可。

继续推，我们可以把右边第i个点展开成a[i]个流量为一的点。

二分图完美匹配。Hall定理，一个二分图存在完美匹配条件是任意一个集合匹配点的个数>=size。

因为右边的a[i]个点的集合都一样，所以边界肯定是都选上这a[i]个点。

所以满足条件：

$\sum_{i\epsilon S}a[i]\leq |S|*(n-1)-|S|*(|S|-1)/2$

所以直接排序之后从大到小前缀和即可。

wiki上给的是从小到大排序满足

$\sum_{i\epsilon S}a[i]\geq |S|*(|S|-1)/2$

两种是一样的。

hdu 5961 传递：

显然是出环就不对了。

然后一个图中若a->b，b->c结果ac之间的边在另一个图里也不行。

其实就是PUQ和PUQ'（Q的边都反向）没有环即可。不用对Q做，因为边都反向结果相同。

bzoj 4727：

就是一个裸的应用了。

能经过的点的个数就是拓扑序上后面的所有点的个数。

然后一次输出同一个强联通分量上的环即可。