之前北大集训中竞赛图找哈密顿回路成为了基本知识点，给我留下了巨大阴影。
趁着摸鱼日补充了一点知识。
参考资料：
兰道定理证明：https://blog.csdn.net/a_crazy_czy/article/details/73611366
Dirac定理和无向图找哈密顿回路（这篇博客我觉得它板子有锅，另外竞赛图部分有太多缺失不能看）：https://blog.csdn.net/u010660276/article/details/44891209
竞赛图找哈密顿路径和哈密顿回路：https://blog.csdn.net/Bfk_zr/article/details/79124479
一些性质：
竞赛图：两两之间都有边的有向图。
竞赛图一定有哈密顿通路，强联通竞赛图一定有哈密顿回路。
竞赛图强联通分量缩点后是一条链，前面的点有连向后面的点的边。
兰道定理：一个竞赛图的比分序列，是把节点出度从小到大排序之后得到的序列。对于一个长度为(n)的比分序列(s_i)，是合法的比分序列（也就是说存在竞赛图使得比分序列是这个）当且仅当(forall 1le kle n,sum_{i=1}^ks_ige inom{k}{2})，(k=n)时取等。
Dirac定理：在一个无向图中，如果对于任意两点(u eq v)有(deg_u+deg_vge n)，则存在哈密顿回路。（充分不必要条件）
推广：当(nge 3)时，如果对于任意点(u)有(deg_uge frac{n}{2})，则存在哈密顿回路。
证明：
考虑维护一条路径(S,v_1,v_2,dots,v_k,T)。先贪心扩展，如果有点和(S)或(T)相邻且不在路径中出现，则把它加到头或尾。
不能扩展的时候，(S)和(T)的所有相邻点都在路径上。
如果(S)和(T)相邻，则找到了个回路。否则，一定可以找到(i)满足((S,v_{i+1}),(T,v_i)in E)（根据(deg_S+deg_Tge n,kle n-2)，反证，假如有分界点使左边只能和(S)相邻，右边只能和(T)相邻，由鸽巢原理得一定不存在），造出回路：(S o v_{i+1} o dots o T o v_i o dots o S)。
找到回路之后，如果长度不为(n)，找一条和回路相连的外面的边，把回路拆成链继续做。
每增加一个点至多进行(O(n))次操作，所以时间是(O(n^2))。
构造竞赛图的哈密顿回路：
类似地搞一条路径(v_1,dots,v_k)。
枚举一个点(x)，如果(x o v_1)就把它放头，找到第一个(i)满足(x o v_{i+1})（此时也有(v_i o x)），把(x)插在(v_i,v_{i+1})之间。如果找不到这样的(i)，一定有(v_k o x)，把(x)放尾。
重复操作一定能造出一条哈密顿通路。
如果图强联通，考虑将其变成哈密顿回路：
维护一个排列(v_1,v_2,dots,v_k,dots ,v_n)，满足(v_i o v_{i+1})，且有(v_k o v_1)（相当于一个环上拉出来一条链）。(k)改变后，先令(i=k+1)。
如果存在(v_{i} o v_1)，则(k)变成(i)。
否则：如果存在(v_{i} o v_j,jle k)，取第一个(j)（一定有(v_{j-1} o v_{k+1})），此时一定有环：(v_{i} o v_j o dots o v_{k} o v_1 o dots o v_{j-1} o v_{k+1} o dots o v_i)，修改顺序并更新(k)为(i)；如果不存在这样的(j)，(i)变成(i+1)。因为强联通，所以当(i=n)时不可能找不到这样的(j)。
最终当(k=n)时，构造完毕。
都是口胡，都没写。