图论

Published: June 18, 2019 by Daltao

• Categories:
• algorithm 101

• Tags:

• Euler Tour Tree
• 连通性检测
  • 离线线段树做法
  • 特殊情况做法
  • 离线LCT做法
  • 在线做法
  • 删边判连通
• 最小环算法
  • Floyd求法
  • 有向图最小环
  • 无向图最小环
• 一类最小瓶颈路问题
• Erdos-Gallai定理与Havel–Hakimi算法
• 支配树
• 二分图邻集问题
• 竞赛图（Tournament）
• 点双连通分量
• 圆方树
• 强连通分量
  • 有向图强连通最少需要加入边数
• 子图状压问题
• Tutte多项式
  • Reliability polynomial
• 图上亦或问题
• 唯一路径问题
• 一类图上标号问题
• 支配集
• 哈密顿问题
• 子图划分问题
• 负环
• 建图问题
• 欧拉子图相关问题
• 失去连通性最小费用
• 矩形网格图哈密顿路径
• Lindström–Gessel–Viennot lemma
• 关键点
• 可达树
• 图划分问题
  • 边划分问题
• 参考资料

Euler Tour Tree

Euler Tour Tree也是动态树，支持$O(\log_2n)$的换根，加边，删边操作。类似于Link-Cut-Tree，但是底层原理是将树表示为DFS序，并将DFS序放到平衡树上去维护。

要了解更多，可以去阅读斯坦福大学的课件，地址如下：

http://web.stanford.edu/class/archive/cs/cs166/cs166.1146/lectures/05/Slides05.pdf

Euler Tour Tree和Link Cut Tree的区别在于，后者是以Splay森林保存信息，每个森林中的树都代表一条树上的路径，因此Link Cut Tree非常适合用于处理路径问题。而前者是以一株平衡树进行维护的，因此可以很好的利用树的一些性质，比如处理子树问题。

连通性检测

对于一个含有n个顶点的无向图，一开始边集为空。你需要处理m个请求，请求内容为下面三类：

1. 增加一条边
2. 删除一条边
3. 判断两个顶点是否处于相同相同的连通块中

离线线段树做法

现在我们换个角度来理解问题，有m个时间点，每个时间点，每个请求都会修改某个时间区间的状态。最后要求在所有请求完成后，每个时间点的状态。

这涉及到了区间修改和单点查询，妥妥的就是线段树啊。我们可以把每个请求看成一个事件，事件从某个时间点$L$起到某个时间点$R$结束。我们可以用线段树来存储事件，但是特殊的是，我们不下推时间，即如果有一个线段树顶点代表的区间被某个时间完整覆盖，那么我们将这个事件绑定到这个顶点上，而不继续下推。

很容易证明每次请求最多会修改$\log_2m$个顶点。而最后查询的时候我们在进入顶点的时间执行所有的事件（合并连通块），而在离开顶点的时候撤销所有事件（分裂连通块），由于连通和分裂是一个栈式操作，因此我们可以用不带路径压缩的并查集来维护连通块。由于每个事件只会被处理两次（执行和撤销），而总共有$m\log_2m$个事件，每次合并分裂的时间复杂度均为$\log_2n$，因此总的时间复杂度为$O(m\log_2n\log_2m)$，空间复杂度为$O(m\log_2m+n)$。

特殊情况做法

如果存在某个特殊的数$x$，满足前$x$个请求都是加边，而后$m-x$个请求都是删边操作，那么我们可以以线性时间复杂度计算出结果。

具体做法如下。容易发现没有删除操作的情况下，只需要用并查集就可以维护所有连通块，因此前$x$个请求一定能在线性时间复杂度内完成。现在考虑后$m-x$个删除操作。假如删除操作完成后，我们进行回退，会发现我们只需要执行$m-x$个增加操作即可。因此结果还是$O(m-x)$。

总的时间复杂度和空间复杂度都是线性的。

离线LCT做法

如果题目可以允许我们离线，我们可以用Link-Cut-Tree轻松解决这个问题。按序处理请求：

1. 假设要加的边为e=(u,v)，我们先检查后面第一个删除边e的类型三请求出现的序号，记作t，将e的寿命设为t。假如此时u和v不连通，那么就直接插入e，用e将u和v连通。否则，我们判断u和v所在路径中寿命最短的边z，判断z的寿命是否小于e的寿命，如果小于，删除z加入e，否则忽略e。
2. 不处理。
3. 假设要处理的顶点对为u、v。先判断u、v是否连通，不连通，则必定不连通。如果连通，就判断u、v之间路径上寿命最短的顶点z，如果z的寿命小于当前请求的序号，则不连通，否则连通。

利用离线做法，我们每次请求都变成了常数次LCT操作，总的时间复杂度为$O((n+m)\log_2n)$。

题目1：给定一个包含$n$个顶点的，开始的时候没有边。之后$m$个操作，每个操作指定一条边，如果边不存在，则插入，否则删除。要求在每个操作完成后，判断当前图是否是二分图。其中$n,m\leq 2\times 10^5$

题目

首先我们可以转换一下问题，将问题改写为，有若干条边，边有出现时间和删除时间，从时间$1$到时间$m$，问图是否是二分图。

一道比较有趣的题目。众所周知，一个图是二分图，当且仅当它没有奇环。

因此我们考虑插入一条边和删除一条边后快速判断图中是否存在奇环。维护一个边$T$，考虑现在处理第$i$个请求。假设要求插入一条边，如果没有形成环，那么图的奇偶性是不会改变的。否则形成环，分两种情况讨论：

• 形成的是偶环。这时候我们选择环上最早被删除的边删除。
• 形成的是奇环。我们记录环上最所有边的删除时间的最小值$t$，将$T$更新为$\max(t, T)$。同时删除环上最早被删除的边。

利用LCT以及离线化，上面的算法可以在$O((n+m)\log_2n)$时间复杂度内解决。下面我们证明算法的正确性。

在没有形成环的情况下，我们确实插入了一条边$(u,v)$，并且没有形成额外的环，因此这一步是正确的。考虑形成偶环的情况，假设被删除的边为$(a,b)$，我们可以保证，如果之后在原图中出现了包含边$(a,b)$的环，那么在我们维护的生成树中会出现一个包含$(u,v)$的与其奇偶性相同的环。最后考虑奇环的情况，由于出现了奇环，且奇环上最早被删除的边的删除时间为$t$，那么对于之后到第$t$个请求前，图都是包含奇环的，因此所有后面的边，我们都可以将其出现时间推迟到$t$或之后（因为这个时间新插入的边不能影响图是否是二分图）。基于这个假设会发现，我们的图中始终不会出现奇环，因此我们只需要维护一颗生成树而已。

在线做法

如果问题强制要求我们在线，那么就需要使用euler tour tree来解决问题。

首先我们将边分成$L=\log_2n$层。对于边e，记Level(e)表示e所在图的层级，边的层级只降不升。同时建立L个图$G_i$，其中$G_i$包含所有n个顶点和所有层级不超过i的边，我们维护它的最小生成树$F_i$，每个边的权重就是它们所在的级别。我们需要维护两个不变的性质：

1. $G_i$中的连通块大小不会超过$2^i$
2. $F_i=F_L \cap G_i$。

维护一个集合E用来保存所有的加入后没有删除的边的信息。接下来按先后顺序处理所有请求：

1. 设新增的边为e=(u,v)，将e加入E，将Level(e)设为L。之后检查$F_L$中u、v是否连通，如果不连通就向$F_L$插入e，否则忽略。

2. 设删除的边为e=(u,v)，先从集合E中删除e。首先如果e不出现在$F_L$中，那么流程直接结束，因为不会影响到连通性。下面考虑e出现在$F_L$中的情况：

   • for i = Level(e) -> L:

     • 从$F_i$中删除e
       • 删除了e并不能保证u、v就不连通了，因为可能存在替换边，我们可以保证假如替换边存在，那么替换边的级别至少是Level(e)，（由最小生成树性质得到）

   • for i = Level(e) -> L:

     • 由于删除了边e，我们将原先u、v所在连通块切分为了两部分，分别记作$B_u$和$B_v$。这里加色和$B_u$的大小不超过$B_v$，考虑到$|B_u|+|B_v|\leq 2^i$，因此$|B_u| \leq 2^{i-1}$，因此我们可以将$B_u$中的全部级别为i的边下推到级别i-1中去
     • 下推$B_u$中的全部级别为i的边到级别i-1中去。
     • for (x, y) in E where Level((x,y))=i and x in $B_u$:
       • if x、y在$F_L$中处于相同的连通块中：
         • 将(u,v)的级别减少1
       • else:
         • 将$(u,v)$加入到$F_i,F_{i+1},\ldots, F_L$中去。并结束过程。

3. 假设要查询的顶点对位u,v，只需要判断在$F_L$中u、v是否在相同连通块中即可。

对于操作1，时间复杂度为$O(\log_2n)$。对于操作2，时间复杂度为$O((\log_2n)^2)$。由于每条边被下放最多$L$次，因此这部分的时间复杂度为$O(m(\log_2n)^2)$。总的时间复杂度为$O(m(\log_2n)^2)$。

删边判连通

考虑给定一个双向图。之后给定$q$个请求，每个请求指定$20$条边，要求判断删除这些边后，图是否丢失连通性（即存在原本连通的点对删边后不连通）。

提供一道题目。

这个用ETT可以$O(20q(\log_2n)^2)$解决，但是还有一种更加快的方法，时间复杂度为$O(20q\times 64)$。

具体做法如下：

首先我们找到其中的任意一株生成树，为每个非树边赋予一个随机值。之后每条树边的权值设置为所有覆盖它的非树边的权值的异或和。之后对于每个请求，考虑删除的边的权重，如果里面存在一个模2意义的线性相关组，则图将不联通，否则保持联通。

原因如下：

如果图不联通，考虑任意一个连通块，可以发现一个端点位于这个连通块内，另外一个端点位于连通块外的非树边都已经被删除了，而这个连通块到原本父亲结点的边的权值正好是所有这些提到的非树边的异或和，因此此时一定存在一个线性相关组。

当然即使图保持连通也可能会发生误判，即依旧存在线性相关组。这时候可以用更长的二进制来降低概率。

最小环算法

Floyd求法

Floyd算法也可以用于解决最小环问题。所谓的最小环问题，是指在图中找到一个总边权最小的长度至少为3的简单环，时间复杂度为$O(V^3)$。

考虑最小环C，设C上编号最大的顶点为x，记x左右两边的顶点为u，v，C上边的总权重为c，那么必定有

$$c=D(u,v,x-1)+D(v,x,x-1)+D(x,u,x-1)$$

我们可以在Floyd流程套入计算最小环的过程。

c = INF;
for(k = 1; k <= n; k++){
    for(i = 1; i <= n; i++){
        for(j = 1; j <= n; j++){
            if(i != j && edges[j][k] && edges[k][i]){
            	c = min(c, D[i][j]+D[j][k]+D[k][i]);
            }
        }
    }
    for(i = 1; i <= n; i++){
        for(j = 1; j <= n; j++){
            D[i][j] = min(D[i][j], D[i][k]] + D[k][j]);
        }
    }
}

有向图最小环

要求有向图的最小环，可以通过全源最短路径实现。以每个顶点作为源，找到回到自己的最短路，这样就构成了最小环。从这些最小环中取最小的，就是我们要求的结果。

用Dijkstra算法总的时间复杂度为$O(V(V+E)\log_2V)$，如果是单位权图，那么可以用BFS算法将时间复杂度优化到$O(V(V+E))$。

无向图最小环

如果图中有自环，那么我们就找到了最小环，长度为1。否则如果图中有重边，我们就找到了最小环，长度为2，接下來仅考虑无自环和重边的简单图，这时候环的长度至少为$3$。

由于最小环中必定含有一个顶点，因此对每个顶点枚举包含它的最小环，之后合并后就能得到整个图的最小环。那么下面我们要解决的问题是：给定某个顶点$r$，找到包含它的最小环。

我们可以算出以$r$为源的单源最短路径（如果有多条，我们任选一条），之后由于每个顶点（除了$r$）的最短路都有前驱顶点，我们将前驱顶点作为树父，这样就形成了一株以$r$为根的树。

这里我们将除了$r$外顶点进行标记，对于顶点$v$，如果到$v$的最短路为$r=x_1,x_2,\ldots, x_k=v$，那么$v$的标记为$x_2$，记作$tag(v)$。于是每个顶点都得到了一个标记（除了$r$）。现在考虑一条边$(u,v)$，其中$u$与$v$均不是$r$，且$tag(u)\neq tag(v)$，那么我们就找到了一个有效环$r..u,v..r$。

上面这个算法我没有严谨的证明。

时间复杂度和有向图是相同的，用Dijkstra算法总的时间复杂度为$O(V(V+E)\log_2V)$，如果是单位权图，那么可以用BFS算法将时间复杂度优化到$O(V(V+E))$。

提供一道题目。

一类最小瓶颈路问题

问题1：有无向图，有n个顶点，m条边。你从顶点1出发，去往顶点n。每条边上有一个机关，第i条边会使你损失$c_i$点血量。一旦你血量为负数，那么就会回到起点。每当你抵达一个顶点时，你的血量会完全恢复。问至少需要多少血量，才能保证你能顺利抵达顶点n。

这个问题有比较简单的做法，二分血量，每次校验时，将所有伤害低于血量的边加入，之后判断顶点1和顶点n是否连通即可。时间复杂度为$O((n+m)\log_2m)$。

问题2：有无向图，有n个顶点，m条边。每条边上有一个机关，第i条边会使你损失$c_i$点血量。一旦你血量为负数，那么就会回到起点。每当你抵达一个顶点时，你的血量会完全恢复。现在有Q个询问，每个询问指定一个起点和终点，问分别至少需要多少血量才能顺利从起点出发抵达终点。

这个问题可以通过整体二分解决，总的时间复杂度为$O((m + q)\log_2n\log_2m)$。另外一种做法就是观察出对于起点是u，终点是v的时候，我们实际上要求的从$u$到$v$的最小瓶颈路，而已知最小生成树中每对顶点之间存在的唯一路径都是二者之间的最小瓶颈路，因此我们只需要找到最小生成树，之后用LCT维护整棵树，每个请求都可以以$O(log_2n)$的时间复杂度统计。

问题3：有无向图，有n个顶点，m条边。每条边上有一个机关，第i条边会使你损失$c_i$点血量。一旦你血量为负数，那么就会回到起点。顶点分成两类，第一类顶点具有恢复生命的能力，第二类顶点则没有。现在有Q个询问，每个询问指定一个起点和终点（起点和终点都是第一类顶点），问分别至少需要多少血量才能顺利从起点出发抵达终点。

首先为每个第二类顶点算出其距离最近的第一类顶点的最短距离（利用多源最短路算法）。之后记$d(u)$表示第二类顶点u到最近的第一类顶点的距离。之前我们判断一条边加不加入是靠边的伤害是否不高过血量，现在我们需要修改判断的标准，对于边$e_i=(a,b)$，当且仅当血量不低于$d(a)+d(b)+c_i$。之后问题转换为最小瓶颈路问题，用整体二分或者LCT都可以。

这边说明一下原因好了，假设血量上限为$x$。我们可以定义状态$(i,j)$表示位于顶点i上，并且有j滴血量。我们可以在图上进行搜索来判断是否可以从某个顶点移动到另外的顶点。如果i是第一类顶点，那么由于恢复的效果，因此$(i,x)$可以从$(i,j)$转移抵达，换言之，我们从$(i,j)$到$(i,x)$加上一条有向边。但是i是对于第二类顶点的情况，那么如果$j<d(i)$，那么很显然不能从$(i,j)$转移到血量更高的状态，这也意味着这些状态无法转移到任意顶点为终点的状态，我们可以直接无视这些状态。现在考虑$(i,j)$，其中$x-d(i)\geq j\geq d(i)$，那么我们可以先从这个顶点出发到达最近的第一类顶点之后再次回到当前顶点，从而血量提高到$x-d(i)$，因此我们从$(i,j)$向$(i,x-d(i))$连一条边。事实上，对于任意$(i,j)$，其中i是第二类点，$j>x-d(i)$，都是不可达的，因此我们也可以无视这些状态。

现在我们可以将上面提到的状态和转移进行压缩，我们可以认为顶点$i$对应的就是状态$(i,x-d(i))$（这是可达的并且可以通过后续转移抵达某个第一类顶点的最优状态）。现在我们考虑边$e_k=(a,b)$，我们是否可以从$(a,x-d(a))$转移到$(b,x-d(b))$呢，这要求我们经过边$e_k$从a到b后剩余的血量至少不少于$d(b)$，即$x-d(a)-c_k\geq d(b)\Rightarrow x\geq d(a)+d(b)+c_k$。这就是题解中公式的由来。

问题4：有一颗有$n$个顶点的树$T$，顶点分成两类，第一类具有恢复效果，第二类则没有。经过第$i$条边，会受到$c_i$点伤害($1\leq c_i\leq 5$。初始的时候或者抵达第一类顶点的时候血量会恢复到$k$（一旦血量为负则会直接失败）。现在给出$q$个请求，每个请求给定两个顶点$(u,v)$，要求回答是否有可能从$u$出发抵达$v$，不保证$u,v$是第一类点。

如果能保证每次起点和终点都是第一类顶点的话，这个问题实际上就成为了问题$3$的弱化版。但是这里不保证。

如果没有第一类顶点，那么我们每次只能选择最短路，这条路是树上的唯一路径。因此比较一下血量不小于路径长度即可。

首先我们将所有边切分成单位为0.5的边（比如边的伤害为2，我们就切成四条边，中间创建三个临时顶点）。这样一条边最多切成了$10$条边，而我们可以对应的将血量翻倍。现在问题就成了有一副图，经过每条边都会受到一点伤害，而你的血量是$2k$。

我们可以尝试建立这样一幅图$G$，如果两个第一类顶点的距离不超过$2k$，那么我们可以自由通行与这两个顶点之间，于是我们在$G$上将这两个顶点上建立一条边。对于图$G$，如果两个顶点连通，那我们对应的在树上就可以进行相互转移。由于图$G$只有连通性有用，因此我们可以直接通过维护一个并查集实现。可以证明任意一个$G$中连通块对应的都是一株原树的子树（连通块在$T$中依旧保持连通）。

下面我们考虑怎么求$G$，我们当然可以对每个顶点跑一次单源最短路，但是这样太慢了。我们可以对于每个第一类顶点$v$求出距离它小于等于$k$的顶点，并将它们并入到$v$所在的连通块中。这样任意两个距离不超过$2k$的顶点对，它们的连通块必定会有交集。当然这样求$G$还是太慢了，我们可以换一种做法。先以所有第一类顶点作为起点抛出多源最短路径。之后如果某个顶点$x$距离最近的第一类点$y$的距离小于$k$，那么它的邻近的顶点$z$自然是属于$y$所在的并查集的，事实上我们可以保证$x$与$y$属于相同的并查集，因此我们只需要将$x$与$z$合并即可。这样我们只需要$O(n+n\alpha(n))$的时间复杂度就可以算出$G$中的所有连通信息了。

现在考虑一个请求$u$到$v$。很显然对于一个请求，我们有两种选择，第一种就是不在任何第一类顶点上休息，第二种就是进行了至少进行了一次休息。第一种请求求一下树上路径长度即可，通过差分+求LCA就可以直接解决。下面考虑第二种情况。这时候我们发现$u$到$v$的路径上被切分成若干段，每一段都属于$G$上的不同连通块。第二种选择的策略实际是这样的，我们先移动到某个连通块的边缘顶点$x$，之后去往同一连通块中最近的第一类顶点恢复，之后转移到距离$v$最近的且与当前所在第一类顶点在属于相同连通块的某个顶点$y$，之后从所在处去往$v$。

但是这里我们抵达$x$后需要保留$k$点血量以保证能到达最近的第一类顶点，同理$y$由于与$v$不属于相同的连通块，因此$y$距离一定处于所在连通块的边缘，即此时剩余的血量正好为$k$。

换句话说，$u$到$x$的距离不能超过$k$，而$y$到$v$的距离也不能超过$k$。现在问题变成，如果两个人分别从$u$最多走$k$步，$v$最多走$k$步，问是否有可能两个人最终处于相同的连通块。

考虑到$G$上的连通块是对应$u$到$v$路径上连续的一段，而$u$到$v$的距离超过$2k$。于是乎显然我们应该向彼此尽量靠近，即分别向对方走$k$步，最后判断一下是否处于相同的连通块即可。

提供一道CF题目。

Erdos-Gallai定理与Havel–Hakimi算法

给定一个包含$n$个顶点的无向简单图（无重边），以及每个顶点的度$d_1,d_2,\ldots,d_n$，问是否存在这样的图，如果存在就构造出来。

如何判断图是否存在.首先有解的前提是度数之和为偶数且所有度数非负。

Erdos-Gallai定理给出了一种$O(n)$时间复杂度的检查方法。其命题如下：

假设度数从大到小排序，$d_1\geq d_2\geq \ldots \geq d_n$，那么如果对于所有$1\leq k\leq n$，下面公式都成立，那么就有解，否则无解。

$$\sum_{i=1}^kd_i\leq k(k-1)+\sum_{i=k+1}^n\min(d_i,k)$$

这个公式可以通过一些预先处理，在$O(n)$时间复杂度内计算完成。

那么现在知道有有没有解后，如何构造一组解呢。

很显然构造一组解的时间复杂度至少为$O(D)$，其中$D$是所有顶点的度数的和。我们可以用 Havel–Hakimi递归算法来实现。方法如下，我们将所有顶点按度数从大到小排序后，顶点$1$与$2,3,\ldots, d_1+1$建立一条边。之后我们递归解决剩下的包含$n-1$个顶点且度数分别为$d_2-1,d_3-1,\ldots, d_{d_1+1}-1, d_{d_1+2}, \ldots, d_n$的无向图构建问题。

Havel–Hakimi算法的总的时间复杂度为$O(n^2)$，排序可以选择将修改部分和未修改部分合并或基数排序。

支配树

详细的内容可以见CF博客。

支配树可以解决这样一类问题：

给定一副有$n$个顶点$m$条边组成的有向图（允许有环），并选择一个顶点$r$作为根。对于可以被$r$访问到的每个顶点$v$，找到所有顶点$u$，满足删除$u$后，无法从$r$移动到$v$。这样的顶点对$u,v$，称作$u$支配$v$。

我们会发现支配关系满足传递性和反对称性。于是我们可以将支配关系建立成一个以$r$为根的树形图，一个顶点被其所有祖先顶点支配。

支配树可以以$O(n+m\log_2n)$时间复杂度内创建。

提供一道luogu模板题。

那么建立了支配树后，如何判断某个顶点是否支配另外一个顶点呢，判断两者的LCA是否是前者即可。提供一道支配树+LCA的CF题目。

二分图邻集问题

问题1：给定一个二分图，左边有$L$个顶点，右边有$R$个顶点，以及$m$条边。右边第$i$个顶点上都写了一个正整数$a_i$。对于$L$的任意子集$S$，记录$N(S)$表示$S$的邻集，而记$f(S)$表示$S$的邻集上的数字之和。现在问所有$2^L$个$L$的子集$S_1,\ldots,S_{2^L}$，要求计算$gcd(f(S_1),\ldots,f(S_{2^L}))$，其中$L,R,m\leq 10^6, a_i\leq 10^{12}$。

首先如果有多个右边顶点，它们的邻集相同，那么就将它们合并成一个顶点（因为会被同时选择），而权重为这些顶点的权重之和。

假设结果为$g$，那么$g$一定是$\sum_{i=1}^Ra_i$的因子。我们可以一开始枚举$g=\sum_{i=1}^Ra_i$。之后如果所有右边顶点的权值都能整除$g$，那么显然不可能有更小的结果了，这时候就可以直接退出。

否则，我们找到权值不能整除$g$的右边顶点中，度数最小的那个顶点$v$，之后我们选中$L/N(v)$。对于度数能整除$g$的左边顶点，是否选中不会影响结果，而对于不能被$g$整除的其余顶点，我们会发现由于不同顶点的邻集不同，且$v$的邻集是其中最小的，因此该顶点的某个邻接顶点一定属于$L/N(v)$。

之后我们来计算$f(L/N(v))$在模$g$的时候的值，很显然值恰好为$\sum_{i=1}^Ra_i-a_v\pmod g$。这个值不是0，即$f(L/N(v))$的总权不能整除$g$，这意味着我们可以得到更小的公约数。

由于$g$最多减少$\log_2 10^{18}$次，因此总的时间复杂度为$O(m+L+R\log_210^{18})$。

其实还可以简化一下，因为得到的结果一定是所有顶点权重的最大公约数的倍数，而上面的过程直到所有顶点权重能整除结果的时候才退出，因此可以得出结果一定是所有顶点（这里的顶点是合并后的顶点）权重的约数。由于最终问题变成了求一组数的最大公约数，而这个算法的时间复杂度为$O(m+L+R+\log_210^{18})$。

提供一道CF题目。

竞赛图（Tournament）

竞赛图是指将一个完全图中的所有边转换成一条单向边得到的有向图。

命题1：如果竞赛图无环，那么竞赛图的拓扑序是唯一确定的

由于无环，因此可以进行拓扑排序。即存在唯一一个顶点（任意两个顶点之间有边，因此这里唯一）出度为0，对应的入度为$n-1$。我们删除这个顶点后，其余所有顶点的出度都对应减少1。而无环竞赛图的子图还是无环竞赛图。重复这个流程，直到所有顶点被删除。这样就得到了唯一确定的拓扑序。

命题2：竞赛图的强连通分量缩点后呈链状

由于竞赛图的连通分块两两有边，且无环。因此我们将连通分块缩点后，得到的是一个更小的无环竞赛图。根据命题1知道它的拓扑序是唯一确定的，因此呈现链状。

命题3：如果竞赛图是强连通的，则一定存在一条哈密顿回路

设$n$为竞赛图的顶点数目。

从竞赛图中任选一个顶点$r$，将竞赛图中有出边到$r$的顶点集合记作$X$，其余顶点记作$Y$。很显然两个集合都不空（否则不可能是强连通分量）。

现在考虑两种情况，如果删除顶点$r$后，剩下的竞赛图依旧强连通，那么我们可以通过归纳法，可以找到其余顶点组成的长度为$n-1$的哈密顿回路。由于是回路，因此存在两个回路中相邻的顶点$u,v$，其中$u\in X$且$v\in Y$。我们可以将$r$插入到回路的$u,v$之间。

否则竞赛图不强连通，此时竞赛图的强连通分量之间呈现链状，且存在链头的某个顶点$v$和链尾的某个顶点$u$，满足边$(r,v)$与$(u,r)$存在。我们可以通过构造法，生成一个长度为$n-1$，且从$v$开始到$u$结束的哈密顿路径，之后加入顶点$r$到路径尾部就得到了回路。

命题4：竞赛图存在一条哈密顿路径

如果竞赛图是强连通的，根据命题3，可以构造一条哈密顿回路。否则竞赛图非强连通，我们可以直接用归纳法处理。

命题5：大小为$n$的竞赛图如果强连通，则恰好有长度为$3,4,\ldots,n$的简单环。

由命题3知道强连通竞赛图一定有哈密顿回路，对应的就是一个简单环。其余环可以通过在哈密顿回路中的$X$集合顶点或$Y$集合顶点删除一些顶点得到。

兰道定理(Landau's Theorem)：一个出度序列$a_1\leq a_2\leq \ldots \leq a_n$，可以构建一个竞赛图当且仅当满足：$\sum_{i=1}^ka_i\geq {k \choose 2}$且当$k=n$时等号成立

必要性不必多说，说一下充分性。

我们可以提前构建一个大小为$n$的无环竞赛图$B$，记$b_i$为第$i$个顶点的出度，且出度满足$b_i=i-1$。

之后我们来考虑如何构造一组解。

如果序列$a$与$b$不同，考虑找到最小的$i$，满足$a_i\neq b_i$。由于无环竞赛图的特殊性质有$\sum_{i=1}^kb_i={k \choose 2}\leq \sum_{i=1}^ka_i$，因此这里一定有$a_i>b_i$。对应的由于$a$序列和$b$序列拥有相同的总和，因此一定存在某个下标$j$，有$a_j<b_j$，且$i<j$。注意到$b_j>a_j\geq a_i>b_i$，因此$b_j\geq b_i+2$。这意味着至少存在某个顶点$t$，$b$到$t$为出边，且$t$到$b$为出边（即存在边$(j,t),(t,i)$）。我们反转这两条边的方向，这样$t$的度数不变，但是$j$的出度减少了$1$，而$i$的入度增加了$1$。且还能发现$b$序列的任意前缀和依旧小于$a$序列的前缀和。

因此不断这与操作，我们就能将构建一个度数指定的竞赛图了。

问题1：给定一个拥有$n$个顶点的竞赛图。告诉你这${n\choose 2}$条边的方向，要求找到其中一个顶点，这个顶点到其它所有顶点都存在一条路径。

当顶点数只有1的时候，很容易求解。现在假设顶点数为$n$，且我们找到了$1,2,\ldots,n-1$的导出子图的一个满足条件的顶点$v$。现在考虑顶点$n$和$v$，如果从$n$到$v$有一条边，那么$n$到其余顶点就都有路径了，同理如果$v$到$n$有一条边，$v$到其余顶点也都有路径了。

问题2：给定一个拥有$n$个顶点的竞赛图。每条无向边有可能有两种颜色，粉色或绿色。现在已知所有粉色的单向边的方向，但是所有绿色边都是未知的。现在要求使用最多$n$次请求，每次请求询问一条绿色边的方向。要求找到其中一个顶点，这个顶点到任意其它顶点，都存在一条仅使用一种颜色边的路径。

首先我们仅考虑粉色边的存在，用tarjan算法处理出强连通分量。

如果此时入边为0强连通分量数目为1，那么任取该强连通分量中的任意顶点作为根即可。否则我们取两个入度为0的不同强连通分量，并从每个强连通分量中各取一个绿边入度为0的顶点，这样一次查询至少一个顶点入度变成了1。如果一个强连通分量中所有顶点的绿边入度都变成了1，就删除这个强连通分量。重复这个操作，直到满足推出条件。

证明一下算法的正确性，首先找到的根由于绿边入度为0，其它顶点要么绿边入度为1，要么就能被根访问到。由于绿边不存在环，因此绿边入度为1的顶点都能被根访问到。

之后每次询问一个顶点入度从0变成1，因此最多发生$n-1$次查询。

一道CF原题。

题目3：给定一个拥有$n$个顶点的竞赛图，要求找出图中所有不同的强连通导出子图（两个强连通导出子图不同当且仅当顶点集合不同），输出它们的顶点集合。$n\leq 23, m\leq n^2$

这道题需要用到竞赛图的特殊性质。竞赛图生成的强连通分量之间是链状关系。这意味着我们可以为竞赛图中的极大强连通分量排序，记第$i$个强连通分量为$S_i$，如果$i\leq j$，且$a\in S_i,b\in S_j$，那么从$a$到$b$一定存在一条路径。因此我们可以维护一个函数$scc$，其中$scc(x)$表示状态为$x$的导出子图（二进制表示）的编号最小的极大强连通分量中的顶点。之后我们考虑如何计算$scc(x)$，对于任意$x$中的顶点$u$，如果从$u$到$scc(x-u)$中的任意一个顶点有至少一条边，那么$u$一定属于编号最小的强连通分量，即$u\in scc(x)$，对所有$x$中顶点进行考虑即可求出$scc(x)$。

接下来我们来判断一个导出子图$x$是否是强连通的，它是强连通的当且仅当所有顶点位于编号最小的极大强连通分量中，即$scc(x)=x$。

总的时间复杂度为$O(n2^n)$。

推荐一道题目SRM783的RecursiveTournament。

点双连通分量

一个连通块是点双连通的，当且仅当删除任意一个顶点，其余顶点依旧保持连通。但是对于一个仅包含一个或两个顶点的连通块，这个定义是有歧义的。

一般的点双连通分量的求法就是算出dfs树，之后每加入一条非树边都会形成一个新环，相同环里的所有边都属于同一个点双连通分量，如果两个点双连通分量有公共边，那么它们一定可以合并为一个点双连通分量。

一个点双连通分量是极大的，当且仅当不存在它的一个超集也是点双连通分量。

可以发现一个顶点如果是割点，那么它会出现在多个极大点双连通分量中。而对于一般点，它只会出现在一个极大点双连通分量中。每条边仅属于一个点双连通分量（如果我们允许存在大小为2的点双连通分量）。

$G=(V,E)$中最多包含$V$个极大点双连通分量，因为每个点双至少会覆盖一条DFS树边。

点双连通分量比较复杂，一种比较好的视角，就是把每个点双视作一个顶点，并且把所有图中的割点加入。如果某个点双包含另外一个割点，那么就在二者之间建立一条边。于是乎点双只和割点相连，割点之和点双相连，且图是无环的，因此是一个森林。

提供一些题目：

• Mining Your Own Business。

圆方树

出处链接。

如果一个图中所有环都没有公共边，那么这样的图称为仙人掌。

我们可以求所有的点双连通分量，并为每个点双创建一个新的结点，这个结点为方点，而原来的顶点为圆点。我们断开同一个点双上的所有边，并将所有点双中的结点与点双对应的方点连边。

可以发现此时得到的新图中不存在环，且依旧保持连通。所有的边都仅连接圆点和方点（类似二分图）。我们选择任意一个圆点作为根，定义一个圆点的深度为到根的最小距离，换言之，就是祖父的深度加上到祖父的最小距离。

得到的新的树就是我们的圆方树。圆方树可以用来解决很多问题：

• 树上两点距离：要找u，v的距离，可以先找到二者lca，如果lca是圆点，那么可以通过深度公式直接求距离，否则lca是方点，我们要找到lca下对应的两个u、v的祖先圆点，并计算二者在这个环上的最短距离。
• 树上直径：处理圆点的时候维护它子树的直径已经最深的结点。之后在处理方点的时候尝试将它们合并。
• 树上DP：对圆点和方点独立处理即可。

强连通分量

一个有向图是强连通的，当且仅当图中任意两个顶点之间存在一条有向路径。

一个无向图是强连通的，当且仅当图中不存在割边。

一个强连通分量是极大的，当且仅当不存在任意一个它的超集也是强连通的。

我们可以用tarjan算法$O(V+E)$时间复杂度内求出一个有向图和无向图的所有极大强连通分块。

用强连通算法可以解决很多问题。

问题1：给定一个有$n$个顶点和$m$条边的有向图，之后给定$Q$个请求，每个请求指定$u,v$，要求判断是否存在一个包含$u$和$v$的环路。其中$n, m, Q\leq 10^6$

存在包含$u$与$v$的环路当且仅当二者处于同一强连通分量。用tarjan算法解决，时间复杂度为$O(n+m+Q)$。

有向图强连通最少需要加入边数

给定一个$n$个顶点$m$条的边的有向图，现在希望加入最少的有向边，使得图中任意两个顶点可达。

一道题目。

首先我们求出所有的强联通分量，之后进行缩点（并删除自环）。现在问题就简单了很多。如果图中只有一个强联通分量，那么结果为$0$。否则，我们计算图中的入度为$0$的顶点数目为$a$，称这类顶点为根，而出度为$0$的顶点个数为$b$，称这类顶点为叶子。很显然要使每对顶点之间都有路径，则每个顶点入度出度都至少为$1$，因此我们得到了一个答案的下限$k=\max(a,b)$。下面我们设计一套仅需使用$k$条边的方案。

我们在顶点之间连上$k$条边，第$i$条边从第$\min(i,b)$个叶向第$\min(i,a)$个根。可以发现现在所有顶点都有入度和出度。之后我们把所有强联通分量合并，可以发现这些强联通分量中各自至少包含一条我们新加入的边，比如强联通分量$A$中包含的新加入的边为$(u,v)$，而强联通分量$B$中包含新加入的边为$(a,b)$，则要合并$A,B$只需要交换两条边的终点得到$(u,b)$和$(a,v)$即可。最后可以得到唯一的强连通分量。

子图状压问题

问题1：给定一个$n$个顶点的完全无向图，问有有多少不同的生成连通图，即存在多少边集的不同子集，仅考虑这些边，所有顶点连通。

要统计有多少连通图，我们只需要统计有多少不同的非连通图，之后用总子集数$2^{n\choose 2}$减去它即可得到结果。

对于任意一个非连通图，顶点$1$所在连通块大小一定小于$n$。而当顶点$1$所在连通图$S$确认时，对于两个端点都不在$S$中的边，其出现与不出现都可以，但是一个端点落在$S$中的边，一定不出现，而所有两个端点都落入$S$中的边，一定要保证$S$的连通性。

可以发现我们要想求一个大小为$n$的图的连通图数目，需要求大小为$n$的图的不连通图数目，而这可以分解为求一个大小小于$n$的图的连通图数目问题。因此我们这里有效缩小了问题的范围。记$f(n)$表示大小为$n$的完全图，连通图数目。可以得出递推公式：

$$f(n)=2^{n\choose 2}-\sum_{i=1}^{n-1}{n-1\choose i-1}f(i)2^{n-i\choose 2}$$

我们可以直接暴力求解上面的公式，在认为高精度运算（结果范围不会太大）时间复杂度是常数的前提下，得到的时间复杂度为$O(n^2)$。

提供一道POJ题目。

问题2：给定$n$个顶点$m$条边的无向图（可能有重边和自环），要求统计每个导出子图的边集大小，按排序从小到大输出。其中$n\leq 20,m\leq n^2$。

我们记$C(i,j)$表示顶点$i$和$j$之间存在的边数，这个很容易预处理出来。我们可以定义$f(S)$表示$V$的子集$S$对应的导出子图的边集大小。那么我们可以从$S$中取任意一个元素$v$，并记录$S'=S-v$。那么可以得出递推公式：

$$f(S)=f(S')+C(v,v)+\sum_{u\in S'} C(u,v)$$

上面的算法的时间复杂度为$O(n2^n+m+n^2)$，空间复杂度为$O(2^n+n^2)$。

问题3：给定$n$个顶点$m$条边的无向图（可能有重边和自环），要求回答$q$个请求，每个请求选择两个不相交的$V$的子集$A$和$B$，要求计算有多少边一侧端点落在$A$，另外一侧端点落在$B$。其中$n\leq 20,m\leq n^2，q\leq 10^7$。

我们利用问题2的方式求解出每个导出子图的边集大小。之后记$g(A,B)$表示集合$A$与集合$B$之间的边的数目。记录$C=A\cup B$，可以发现$C$的导出子图中的边分成三类，两端都属于$A$，两端都属于$B$，一端属于$A$一端属于$B$，因此可以推出递推公式：

$$g(A,B)=f(A\cup B)-f(A)-f(B)$$

时间复杂度为$O(q+n2^n+m+n^2)$，空间复杂度为$O(2^n+n^2)$。

问题4：给定$n$个顶点，$m$条边的无向图，计算有多少边的子集，能使得图连通。其中$n\leq 15, m\leq 200$。

这道题和问题1类似。要计算多少连通图，我们只需要统计有多少不同的非连通图，而要统计有多少非连通图，我们可以通过统计包含$1$的连通图的数目再乘上某个因子。但是这里不保证是完全图，但是做法还是类似的。

用状态压缩技术，我们可以定义$h(S)$表示$V$的子集$S$的导出子图中连通图的数目。现在我们可以得出递推公式，记$E(S)$表示集合$S$的导出子图的边集。可以推出递推公式：

$$h(S)=2^{E(S)}-\sum_{X\subset S\land 1\in X}h(X)2^{E(S-X)}$$

通过预处理，这个方法的时间复杂度是$O(n2^n+3^n)$。

问题5：给定$n$个顶点，$m$条边的无向图，要求对于所有$n-1\leq k\leq m$，计算有多少大小为$k$的边集的子集，能使得$n$个顶点连通（这个结果记作$f(k)$）。其中$n\leq 15, m\leq 200$。

Topcoder 761 SpanningSubgraphs

目前不会。。Petr在他的博客给了做法，有兴趣的人可以参考。

现在会了。首先我们可以考虑这样一个函数$h(p)$，表示每条边都有$p$的独立概率被删除，问最后图保持连通的概率。

很显然$h(p)$是Reliability polynomial，其是Tutte多项式的变种，且是一个阶数不超过$m$的多项式。

要得到$h(p)$，我们可以通过插值法。对于给定的$p_0$，我们可以用问题1的相同方法$O(3^n)$求解出$h(p_0)$，同理，我们只需要计算出$m+1$个输入输出对，就可以得到$h(p)$，时间复杂度为$O(m3^n)$。

同时我们可以发现$h(p)=\sum_{i=0}^mf(i)p^{m-i}(1-p)^i$。我们可以从$h(p)$的系数中提取出$f(i)$。

总的时间复杂度为$O(m3^n+m^3)$。

问题6：计算存在多少$n$个顶点的竞赛图，整个图是强连通分量。其中$1\leq n\leq 10^4$。结果对素数$p$取模。

首先竞赛图缩点后得到的是一条链，这意味着只存在一个强连通分量，到所有顶点都有一条边，我们称这个连通分量为根。

记$f(k)$表示$k$个顶点的竞赛图，有多少形成强连通分量。我们可以从全集中减去那些不能形成强连通分量的竞赛图数量就是结果，为了避免重复统计，一个比较好的方法就是我们直接枚举根连通分量。即

$$f(k)=2^{k\choose 2}-\sum_{i=1}^{k-1} {k\chosoe i}f(i)2^{k-i\choose 2}$$

很显然我们可以$O(n^2)$解决这个问题。

Tutte多项式

无向图$G=(V,E)$的Tutte多项式的定义为：

$$T_G(x, y)=\sum_{A\subseteq E}(x-1)^{c(A)-c(E)}(y-1)^{c(A)+|A|-|V|}$$

其中$c(A)$表示仅保留$A$中的边，图中的连通块数目，对于$c(E)$同理。

可以看出$T_G(x,y)$的$x$项的最高指标为$|V|$，而$y$项最高指标为$|E|$。

Reliability polynomial

给定无向图$G=(V,E)$，每条边都有$p$的概率被删除，不同边的删除是独立的。问最后图保持连通的概率$R_G(p)$。

$$R_G(p)=T_G(1, p)$$

可以发现$R_G(p)$是$p$的$|E|$阶多项式。

图上亦或问题

考虑这样一个题目：给定一个序列$a_1,\ldots,a_n$，每个元素初始的时候都是$0$。之后由$m$次操作，第$i$次操作给定两个数$x_i$和$y_i$，你必须$a_{x_i}$或$a_{y_i}$中的一个亦或上1。且要求$m$次操作后$\sum_{i=1}^na_i$最小。

对于每个序列中的元素，建立一个顶点，对于第$i$个请求，我们可以在$x_i$和$y_i$之间建立一条无向边。对于不同的连通块，我们可以独立处理。现在仅认为只有一个连通块。

我们可以重新解释问题，我们希望为每条无向边与其一个端点匹配，称与某个顶点匹配的边数为这个顶点的匹配度，我们希望让拥有奇数匹配度的顶点尽可能少。同时我们发现，对于一条简单路径，我们如果取反上面的所有边（即让边与另外一个顶点匹配），我们会发现仅路径的起点和终点的匹配度的奇偶性会发生改变。因此我们可以生成任意一个生成树，并任选一个顶点为根。将每个奇度数的顶点到根的路径全部翻转，这样我们发现除了根外，其余顶点的匹配数都是偶数。根的匹配度决定与连通块中边数的奇偶性，如果边数为奇数，那么根的匹配度也是奇数，这是无法避免的（不可能所有顶点的匹配度都是偶数）。

上面的过程，可以$O(n+m)$完成。

上面这个题目还有一个经典的变形：给定一副简单无向图（无重边和自环），我们希望重复尽可能多次下述操作：选择一个三个顶点$x,y,z$，其中边$(x,y)$和$(y,z)$存在，删除这两条边。问我们可以最多执行该操作多少次，并输出一个最长的操作序列

这个问题和之前提到的问题是一样的。为啥。我们可以重新解释该操作，选择某个顶点$y$，删除与其相邻的两条边，问最多删除次数。这等价于将每条边与某个端点匹配，如果一条边和某个端点匹配，称与某个顶点匹配的边数为这个顶点的匹配度，记$deg(i)$为顶点$i$的匹配度。那么我们希望最大化的是$\sum_{i=1}^n\lfloor \frac{deg(i)}{2}\rfloor=\frac{m-\sum_{i=1}^n(deg(i)\pmod 2)}{2}$。这等价于最小化拥有奇数匹配度的顶点。剩下的就和之前提到的问题是一样的了。提供一道题目。

唯一路径问题

一条简单路径是指一个无重复的顶点序列，其中对于任意相邻的有序顶点对$u,v$，都存在$(u,v)$这条边。

一个顶点如果到其余顶点都有一条唯一路径，则称这个顶点为候选根。

如果是无向图，那么有候选根存在，则意味着图连通，且无环，这意味这是一颗树，此时所有顶点都是候选根。

如果是有向图，问题就变复杂了很多。假设$r$是其中一个候选根，那么以$r$为根的DFS树必然同时满足下面两个条件：

• DFS树一定包含了所有顶点。
• 对于所有的非树边，一定从后代指向祖先。

上面就提供了我们一个$O(V+E)$的算法来判断一个顶点是否是候选根。

下面我们考虑$r$是候选根的情况下，希望找到所有的候选根。我们当然可以用naive的$O(V(V+E))$算法，但是这太慢了，我们实际上可以加速到$O(V+E)$。具体原理是，考虑任意一个顶点$u$，$u$到其子树中的所有顶点都有唯一路径，因此我们需要保证$u$到其所有祖先顶点都有唯一路径。由于$u$可以到其某个祖先顶点，因此在$u$的子树中一定存在一个顶点$v$，以及$u$的某个祖先$a$，$(u,a)$是图中的一条边。如果存在两个这样的顶点，那么路径就无法保证唯一，因此这样的顶点应该恰好只有一个。现在我们从$u$到所有$a$的子树中的顶点都有唯一路径，可以发现如果$u$是候选根当且仅当$a$是候选根。因为$a$要到任意祖先顶点，都不会经过$u$和$u$子树中的顶点。

上面的过程，我们可以通过树上DP在$O(V+E)$求解。

提供一些题目：

• https://codeforces.com/contest/1361/problem/E

一类图上标号问题

问题1：给定$n$个顶点$m$条无向边组成的连通图，要求给每个顶点赋予一个值，记第$i$个顶点的值为$x_i$。要求赋予的值满足$|x_i-x_j|\leq 1$当且仅当边$(i,j)$存在。判断是否有解，如果有解，就输出任意一组解。

CF的题目。

感觉事实上是挺难想到的，我想到将这些顶点按照值进行分组，那么这些组之间应该构成一个有序的列表，同一个组内的顶点组成一个团，任意两个相邻的组之间的顶点的并集也是一个团。然后就没有然后了。

首先我们可以证明如果两个顶点$u,v$的邻接表不同（这里认为一个顶点与自己也是邻接的），那么这一定有$x_u\neq x_v$。否则则必定存在一个顶点$w$，$w\in adj(u)\land w\notin adj(v)$，通过交换$u,v$可以很容易得到这个性质的成立。如果$x_u=x_v$，那么$|x_w-x_v|=|x_w-x_u|\leq 1$，但是这是错误的，因为边$(w,v)$不存在。

同时可以证明在有解的前提下，如果我们把邻接表相同的顶点赋予相同的值，那么依旧是有解的。考虑两个邻接表相同的顶点$u,v$，则边$(u,v)$一定是存在的，因此$|x_u-x_v|\leq 1$。不妨让$x_v=x_u+1$，那么可以发现对于任意与$u,v$相邻的顶点$w$，一定有$x_w\in {x_u,x_u+1}$。可以发现我们在最终结果中将$x_v$从$x_u+1$修改成$x_u$不会影响结果的成立。

因此算法就是我们先合并所有邻接表相同的顶点。之后我们认为图上的每个顶点的邻接表都不同，且每个顶点需要赋予一个与其余顶点均不同的值。

如果一个顶点度数大于$2$，那么其至少有三个邻接的顶点，可以发现我们是无法正确赋值的。

接下来可以发现图中每个顶点的度数都不超过$2$，且图是连通的。那么只有两种情况，顶点构成了一条链表，或者构成了一个环。构成环的情况下，由于所有顶点的邻接表不同，因此环的长度至少为$4$，而在大于$4$的情况下，是无解的。而是链表的情况，我们可以很简单的赋值。

总的时间复杂度为$O(m+n)$，如果我们利用哈希表。

支配集

对于$V$的子集$S$，若对于任意一个顶点$v\in V-S$，其邻集$N(v)$中一定至少有一个$S$中的顶点。那么称$S$是支配集。所有支配集中最小的称为最小支配集。

对于图中的某个大小为$k$的连通块，其中$k>1$，其最小支配集的大小上界为$\lfloor \frac{k}{2}\rfloor$。因为我们可以搞出一个生成树，之后将偶数深度的顶点和奇数深度的顶点分成两个集合$A$和$B$，可以发现二者都是这个连通块的支配集，且$|A|+|B|=k$。

题目1：给定$n$个城市，可以在一些城市中安装雷达，雷达的作用范围是半径为$r$的圆，此时城市可以视作一个点。现在知道每个城市的坐标，问至少要安装多少个雷达，可以将每个城市覆盖在雷达范围内（雷达信号边缘也算是覆盖到）。其中$1\leq n\leq 30$

如果两个城市的距离小于等于$r$，我们在他们之间建立一条边。这时候可以发现我们实际上要选的是一个最小支配集。可以用暴力的做法$2^n$，但是加一些优化。

哈密顿问题

题目1：给定$0$到$N-1$共$N$个数字，要求找到这些数字的一个排列$a_0,\ldots,a_{N-1}$，要求对于两个前后相邻的两个数字$x,y$（认为a_{N-1}与$a_0$前后相邻），满足$y=2x\pmod N$或$y=2x+1\pmod N$。或者报告不存在这个排列。其中$1\leq N\leq 10^6$。

提供一道题目。

首先当$N=1$的时候，答案是$0$。否则我们证明当$N$为非$1$的奇数的时候，一定无解。证明就是我们考虑$0$的前驱，其只可能是$(N-1)/2$，但是考虑$-1$的前驱，其只有可能是$(N-1)/2$，因此无解。

接下来我们考虑在$N$为偶数的前提下如何找到一个满足条件的排列。

对于$x$，我们发现它的后继可能为$2x$和$2x+1$，而对于$x+n/2$，它的后继也只有可能是$2x$和$2x+1$。同理数$2x$和$2x+1$的前驱只有可能是$x$或$x+n/2$。我们可以简单起见，将$x$的后继设置为$2x+\lfloor \frac{x}{n/2}\rfloor$。可以发现每个数的出度和出度都为$1$，换言之，现在的所有整数组成了若干个哈密顿环路。

接下来我们试着将所有哈密顿环路合并。一般情况下，这是不可能的（或者很难完成），但是在这个特殊的图下，是一定可能的。

命题：如果现在有至少两个哈密顿环存在，则至少存在一个$x$，$x$和$x+n/2$处在不同的环中。

用反证法，假设所有的$x$和$x+n/2$都处在同一个环中。考虑$0$，由于$0$和$n/2$处于相同的环中，因此$0$和$1$处在相同的环中。接下来用归纳法，如果已知道$[0,m]$处于相同的环中，则一定有$[0,2m+1]$处于相同的环中。因此，可以发现所有的整数都处于相同的环中，这与存在至少两个哈密顿环的前提相悖。

根据命题，我们可以检测所有的$x$和$x+n/2$是否处于同一个环，如果不是，则交换$x$和$x+n/2$的后继就可以实现两个环的合并。

上面的过程，我们只需要用到并查集，时间复杂度为$O(n\alpha(n))$。

子图划分问题

题目1：给定一个无向带权完全图$G=(V,E)$，任意两个不同的顶点之间都有一条无向边。现在要求将图中顶点集合$V$划分为若干个集合$V_1,V_2,\ldots,V_k$，其中每个集合$V_i$都满足对于任意两个端点落在$V_i$中的边$a$，以及任意一个正好一个端点落在$V_i$中的边$b$，都有$w(a)<w(b)$成立。问对于$k=1,2,\ldots,n$，不同的划分数，结果对素数$p$取模。其中$1\leq n\leq 2000$。

提供一道题目。

这里我们简单将满足$V_i$条件的集合称为好集合。我们首先看一下如何统计好集合的数目。

首先所有的一个顶点组成的集合一定是好集合。之后我们可以发现如果一个集合$X$是好集合，记$R$为两个端点都落在$X$中的权重最大的边的权重（如果不存在，则设做无穷）。我们考虑所有权重不超过$R$的边，则$X$中顶点与其余顶点之间没有连边，即它是一个单独的连通块。因此我们可以提前对所有边进行排序，之后在做kruskal算法的时候可以记录每个连通块的大小和边数，这样就能判断所有的好集合了。可以发现好集合最多有$2n-1$个。

接下来我们考虑如何统计结果，即将$V$划分成好集合。做法也是类似，在做kruskal算法的时候，我们为每个连通块维护一个dp数组，其中$dp(i)$表示这个连通块分解为$i$个好集合的方案数。在两个连通块合并的时候，我们的DP实际上做一个卷积。但是可以发现这实际上是树上的DP操作，这种类型的DP的时间复杂度为$O(n^2)$。

如果在对边排序的时候使用基数排序，这样总的时间复杂度近似于$O(n^2)$。

负环

下面我们讲一下如何判断图中存在负环。我们可以用SPFA算法来判定，如果一个顶点离开队列超过$V$次，则一定存在负环。原因如下：我们可以记$D(i)$表示从起点到顶点$i$的最短路上的边数（如果有多个最短路，就取边数最少的那条）。可以发现在第一轮完成后，所有$D(v)=1$的顶点$v$的距离都是正确的，且每个顶点最多出队一次。由于在无负环的情况下，最短路上不会出现重复顶点，因此，可以发现$D(v)\leq n-1$，对应的每个顶点最多出队$n-1$次。但是这里有一个特殊的情况，就是顶点只有一个的时候，这时候起点无论如何都会出队，因此我们可以保证每个顶点出队的次数不会超过$V$。

接下来讲一下如何的到完整的一个负环。具体做法就是从任意一个出队次数超过$V$的顶点开始，可以发现起点到它的路径中一定存在两个重复顶点，换言之一个环。不难发现这个环是一个负环。我们可以DFS找到这个环。

建图问题

题目1：给定$n$个顶点，要求加入$kn$条有向边，且每个顶点的入度和出度正好为$k$。要求这样的图还满足任意两点之间的最短距离不超过$m=\lceil \log_k n\rceil$。

我们将顶点从$0$开始编号，给第$i$个顶点加入的第$j$条边是$(i,ik+j-1\pmod n)$。

下面我们证明这样的图是满足条件的。对于从任意数值$x$开始，我们从$k$进制来观察它，在不考虑取模的情况下，它每移动一步，$x$会左移一次并设置最后一位。因此移动$m$次后，其可以达到的范围为$k^mx+0,k^mx+1,\ldots,k^mx+k^m-1$，这是连续的$k^m>n$个值，因此即使在模$n$的情况下，也可以保证$0,\ldots,n-1$都被覆盖到。

提供一道题目。

欧拉子图相关问题

对于无向图$G=(V,E)$，考虑$E$的某个子集$E'$，如果$G'=(V,E')$中每个连通块都可以表示为一个欧拉闭迹，那么称$G'$是$G$的欧拉子图。

可以发现，两个环的异或也是一个环（可能是空环）。类似的，两个欧拉子图的异或一定还是欧拉子图。

考虑$T$是原图的任意一个生成树，而很显然对于任意$E-T$中的边$e$，加入生成树后一定会形成一个简单环。取这个简单环，记作$C(e)$。

考虑$E-T$的任意子集$X=\left\{x_1,x_2,\ldots,x_k\right\}$，记$L(X)=C(x_1)\oplus C(x_2)\oplus \ldots \oplus C(x_k)$。很显然$L(X)$一定是一个欧拉子图。这里我们证明了任意$E-T$的子集$X$，一定存在一个欧拉子图$C(X)\subseteq X\cup T$，且$X\subseteq C(X)$。

接下来我们证明$X\cup T$的所有欧拉子图中，只有$C(X)$是$X$的超集。考虑任意一个同样满足条件的欧拉子图$Z$，且$Z\neq C(X)$，由于$Z\oplus C(X)$也是欧拉子图，且$Z\oplus C(X)\subseteq T\land Z\oplus C(X)\neq \emptyset$，这意味着$T$中存在环，这与$T$是树的前提相悖。

因此对于任意给定的$X$，我们能找到唯有的欧拉子图，包含$X$中所有边，且不包含$E-T-X$外的其余边。这也说明了欧拉子图的数目等于$2^{E-T}$。

题目1：给定$n$个顶点$m$条边的无向图，统计图中的欧拉子图数目。

提供一道题目。

失去连通性最小费用

这类问题的格式分成两类：第一类是给定两个点$s,t$，问至少删除多少顶点（不允许删除$s,t$）才会使得$s,t$不能连通。第二类则不给定$s,t$，问至少删除多少边才能使得原本连通的两点不连通。

这类问题可以通过最小割解决，具体的方案是将每个顶点$i$分成两个顶点$L_i$和$R_i$，并加入一条边$(L_i,R_i,1)$，特殊的由于$s,t$不能删除，因此还需要加入$(L_s,R_s,\infty)$和$(L_t,R_t,\infty)$。对于原图的边$(a,b)$，加入一条对应的边$(R_a,L_b,\infty)$。最后跑一次最大流即可。

第二类问题需要求所有点对的最小割，这里可以用上GomoryHu树，这样只需要求$n$次最小割即可。

可以发现对于割点，我们是将点分成两个从而将问题转换为割边问题。同样的对于不允许割的边，我们将其容量设置为无穷来避免被割。

如果问题是删除边而非点，我们自然可以跳过分点的步骤，将可以割的边容量设为$1$，不可割的边容量设置为无穷即可。时间复杂度同样。

矩形网格图哈密顿路径

可以看一下这篇论文。

下面是一些关键点：

记一个整数点$(x,y)$的奇偶性为$x+y\pmod 2$，偶数点着白色，奇数点着黑色。

记$R(m,n)$表示$m$行$n$列的网格图。

网格图$G=(V^0\cup V^1,E)$，满足$|V^0|\geq |V^1|$存在哈密顿路径从$s$到$t$的哈密顿路径的必要条件：

• $G$有偶数个点，且$s$和$t$的奇偶性不同。
• $|V^0|=|V^1|+1$，且$s,t\in V^0$。

如果网格图满足上面条件，则称网格图是颜色兼容(color compatible)的。

下面再提一些必须不满足的禁止条件。

• 删除掉$s,t$后存在两个顶点不连通。
• 如果$(G,s,t)$同构于另外一个网格图$(G',s',t')$，且网格图满足下面条件
  • $G'=R(m,n)$，且$n=3$，$m$为偶数。
  • $s'$的颜色与$t'$以及$G'$的左下角点颜色不同。
  • $s'_x<t'_x-1$或者$s'_y=2$且$s'_x<t'_x$。

如果一个哈密顿路径问题$(G,s,t)$是颜色兼容的，且不满足任意一条禁止条件，那么称这个问题是可接受的。一个哈密顿路径问题有解，则它一定是可接受的。

下面提供一个构造性的证明，来保证所有可接受的哈密顿路径问题，一定有解。

一个宽度为$2$的条状物$S$拆卸一个哈密顿问题$(R,s,t)$如果：

1. $S,R-S$是$R$的一个拆分。
2. $s,t\in R-S$
3. $(R-S,s,t)$是可接受的

如果$(R,s,t)$是可接受的，且$S$拆卸$(R,s,t)$，那么$(R,s,t)$有解当且仅当$(R-S,s,t)$有解。

对于网格图$R(m,n)$，且满足$m\geq n$，如果$v,w\in V(R(m,n))$满足$v_x\leq 2$且$w_x\geq m-1$，那么称$v,w$为antipodes。

如果$(R(m,n),s,t)$是一个可接受的哈密顿路径问题，但是不能被拆分，那么$s,t$为一对antipodes。

考虑一条边$(p,q)$，我们称$(p,q)$划分了$(R,s,t)$，如果存在拆分将$R$分解为$R_p$和$R_q$，满足：

1. $s,p\in R_p$和$(R_p,s,p)$是可接受的。
2. $q,t\in R_q$和$(R_q,q,t)$是可接受的。

如果$(R,s,t)$是可接受的，且$(p,q)$划分$(R,s,t)$，那么$(R,s,t)$有解当且仅当$(R_p,s,p)$和$(R_q,q,t)$同时有解。

如果一个哈密顿问题$(R(m,n),s,t)$既不可被拆卸，也不可被划分。那么我们称这样的问题是原生的。

一个可接受的原生问题的规模仅可能为下面之一：

1. $(m,n)=(5,4)$
2. $n,m\leq 3$

对于原生问题，我们可以暴力枚举并记录解。

Lindström–Gessel–Viennot lemma

算法参考自wiki。

考虑存在一个有向无环图$G=(V,E)$，每条边都有各自的边权。考虑选择$n$个不同的起点和终点，记作$A=(a_1,\ldots,a_n)$以及$B=(b_1,\ldots,b_n)$。定义$w(p)$表示路径上所有边的权重的乘积，定义$e(a_i,b_j)=\sum_{P:a_i\rightarrow b_i} w(p)$，表示从$a_i$到$b_j$的所有路径上边权乘积的和。

下面我们建立一个矩阵

$$M= \left( \begin{array}{ccc} e(a_1,b_1) & \ldots & e(a_1,b_n)\\ \vdots & \ddots & \vdots\\ e(a_n,b_1) & \ldots & e(a_n, b_n) \end{array} \right)$$

那么Lindström–Gessel–Viennot定理则保证了下面等式的成立：

$$\det(M)=\sum_{(P_1,\ldots,P_n):A\rightarrow B} \mathrm{sign}(\sigma(P))\prod_{i=1}^n w(P_i)$$

给定置换$\sigma$，$P_i$表示从$(a_i,b_{\sigma(i)})$的一条路径。而$(P_1,\ldots,P_n)$表示不相交的$n$条路径。而$\sigma(P)$表示由$(P_1,\ldots,P_n)$所确定的置换关系。$\mathrm{sign}(\sigma(P))$表示置换$\sigma(P)$，当其中逆序对为偶数时，结果为$1$，否则为$-1$。

关键点

给定一个有向图$G=(V,E)$，一个顶点$u$称为关键点，当且仅当，对于任意顶点$v$，要么存在一条从$u$到$v$的路径，要么存在一条从$v$到$u$的路径。要求找出所有的关键点。

很显然同一个强连通分量中的点要么同时都是关键点，要么都不是，我们先将强连通分量进行缩点。现在我们可以认为图中每有环。

很显然存在一个用bitset进行优化的算法，时间复杂度为$O(EV/32)$。下面我们讲一个时间复杂度为$O(V+E)$的算法。

对于无环图，它实际对应一个偏序关系。那么一个关键点，实际上就是一个特殊的点，它可以与所有顶点进行比较。

我们将图按照拓扑序进行分层。一个顶点如果没有出度，那么它处于第一层，否则它处在第$l+1$层，其中$l$为它能直接到达的顶点所在层的最大值。

对于处在相同层的顶点，由于它们之间一定不存在路径，因此它们一定不能被比较。如果这个层中至少有两个顶点，那么这个层中的所有顶点都不是关键点。

现在我们得出了关键点的必要条件，必须独占一个层，这时候可以同时推出之后的所有层次中的顶点都必定能抵达这个顶点。但是光这个还不够，从它出发必须能抵达所有之前层的顶点。

我们可以遍历所有层，并且维护一个集合$S$，表示目前不可达的顶点。初始的时候为空。

之后按照编号从小到大遍历每一层，考虑层中的所有顶点，删除$S$中的可以被这一层的顶点抵达的那些顶点，之后把整层中的所有顶点全部加入到$S$中。如果某一层扫描完成，且$S$中只有一个元素，那么这一层中的唯一顶点就是关键点。

这里我们可以用哈希表或者数组来维护$S$，时间复杂度为$O(V+E)$。

提供一道题目。

题目1：给定一个有向图，其中如果存在边$(u,v)$，那么一定满足$u>v$。现在要求对于$1\leq i\leq n$，判断从$i$是否能抵达所有编号小于它的顶点（存在一条路径）。

按照编号扫描所有顶点，维护一个集合$S$，其中存储扫描过的不可达的顶点。考虑当前扫描的顶点为$u$，那么我们需要删除$S$中所有$u$可达的顶点，之后将$u$加入到$S$中。如果此时$S$中只包含$u$，那么$u$满足条件。

可以发现我们可以$O(V+E)$实现上面这个算法。

可达树

文章地址。下面是个人的翻译和讲解。

给定一个无向图$G=(V,E)$，在上面$O(V+E)$构建可达树。记$G_x$表示仅从$G$中删除权重超过$x$的边得到的图。可达树可以解决下面问题：

1. 找到最小的$x$，满足$G_x$中顶点$u$与顶点$v$连通。可以在线$O(1)$解决。
2. 找到$G_x$中$u$所在连通块的大小。可以$O(\log_2V)$在线解决。

做法非常简单，考虑我们在做最小生成树的Kruskal算法的时候，我们会不断尝试选择最小权重的边。这里我们修改一下流程，初始的时候有$V$个连通块，每个连通块恰好是一个顶点。之后当我们加入一条边$(u,v)$的时候，我们创建一个新顶点$t$，之后在$t$和$u$所在的连通块的根顶点之间加入一条边，在$t$和$v$所在连通块的根顶点之间加入一条边，之后将$u$与$v$所在连通块的根设为$t$。

很显然可达树的大小为$2V-1$。

问题1实际上就是找$u$与$v$的lca，而问题2在线可以用树上倍增做，或者离线查询树上dfs的时候二分根到顶点的路径即可。

题目1：给定一颗大小为$n$的树，结点从$1$到$n$编号。称一条至少包含两个结点的路径是大端路径，当且仅当路径上编号最大的结点在路径的某个端点上。要求统计树上总共有多少大端路径。

我们可以借助dfs树的概念，初始所有结点之间没有边。之后按照编号从小到大进行处理。假设处理的结点为$u$，那么遍历与它相关的边，假设存在边$(u,v)$，满足$u>v$，那么就将$u$和$v$所在连通块中编号最大的结点连边。

这样得到的树非常类似可达树。来看看它有什么性质。$u$与$v$之间的路径，必定经过二者的lca，且路径上编号最大的顶点为它们的lca。如果u不是v的lca且v不是u的lca，那么u、v之间的路径一定不是大端路，反之则必定是大端路。

因此现在问题变成了统计存在多少祖先和后代对。这个非常容易，它等价于所有结点的深度和。

时间复杂度为$O(n)$。

题目2：给定一颗大小为$n$的树，结点从$1$到$n$编号。称一条至少包含两个结点的路径是双端路径，当且仅当路径上编号最大和最小的结点为路径的两个端点。要求统计树上总共有多少双端路径。

提供一道题目。

首先我们可以类似题目1的方式构建一颗大端可达树和小端可达树。现在路径$u,v$是双端路径，当且仅当$u<v$，且$u$在小端树上是$v$的祖先，而$v$在大端树上是$u$的祖先。

我们可以在遍历第一颗树，考虑当前遍历的结点为$x$，维护递归路径信息（祖先信息），之后去第二颗树上查询有多少祖先是第二颗树$x$的后代。我们可以按照第二颗树上的dfs序进行重新编号，那么等价于查询有多少祖先落在某个区间中。我们可以在进入结点的时候让结点对应的位置增加1，离开时减少1，问题求的就是区间和。我们可以用一个二叉索引树来维护。总的时间复杂度为$O(n\log_2n)$。

图划分问题

边划分问题

给定一个无向图，要求将边集划分为若干个非空集合，每个集合都对应一条连续的路径。问至少需要划分为多少个集合。

由于不同连通图可以独立考虑，因此我们现在假设图连通的情形。首先图连通的时候，如果只有最多两个顶点的度数为奇数，则一定可以找到一条欧拉迹，即此时答案为1。考虑奇数度数的顶点数为$2k$，我们实际上可以证明可以划分为k条路径。

由于每条路径最多可以消耗掉两个奇数度数的顶点，因此最小划分至少为$k$。

证明如下，首先我们为这$2k$个奇度数点进行匹配，对于多种匹配，选择其中配对顶点距离和最小的那个。可以发现此时找到配对顶点之间的最短路径，这些路径不会有公共边（否则不是最优匹配）。之后删除掉这些最短路径上的边后，图中所有顶点的度数都是偶数，这意味这可以划分为若干个欧拉闭迹（环）。

对于任意一个环，我们可以选择任意一个有公共顶点的最短路并合并为一条的路径。重复这个过程，我们可以得到正好$k$条路径，即我们将边集划分为$k$个符合条件的集合。

给定一个无向图，边有黑白中某种颜色，要求将边集划分为若干个非空集合，每个集合都对应一条连续的路径，且路径中出现的连续两条边的颜色需要不同。问至少需要划分为多少个集合。

提供一道题目。

由于不同连通块可以独立统计，现在假设整个图连通。

首先我们可以把每条边$e=(u,v)$拆成两个不同点$e_u$和$e_v$（对应两个端点），如果两条边$a$和$b$的颜色不同，并且有公共顶点$t$，则为$a_t$与$b_t$增加一条无向边。

之后很显然原图中的一个划分正好对应新图中的一个匹配。

如果一个路径是闭环，且与另外一个闭环有公共点，则可以合并为一个新的交错环。同理如果一个路径是闭环，与某个交错路径有公共点，则可以合并为新的交错路径。因此我们发现一个匹配中如果有$2k$个顶点未匹配，则可以从中得到一个$k$条交错路径的划分。我们希望交错路径数尽可能少，即我们要找到未匹配顶点尽量少，即最大匹配。

到这里我们能得到一个多项式时间的算法，但是时间复杂度为$O(E^{2.5})$。但是实际上可以继续优化。由于只有对应于端点$t$的边顶点才能匹配，而端点$t$与$t_0$条白边和$t_1$条黑边相连，它能提供的匹配数为$\min(t_0,t_1)$。因此统计所有顶点的能提供的匹配数，就能推出未匹配顶点，即最终路径数。特别的如果某个连通块（至少有一条边）未匹配顶点为0，则需要一条路径。这样我们得到一个$O(V+E)$的算法。

参考资料

• 最小生成树的一些性质和理解
• 斯坦福课件
• https://pdfs.semanticscholar.org/a35c/cea03eb856b6f13908d8db78aeef47bc6819.pdf
• https://zh.wikipedia.org/wiki/Floyd-Warshall%E7%AE%97%E6%B3%95
• https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Gallai_theorem
• https://en.wikipedia.org/wiki/Havel%E2%80%93Hakimi_algorithm
• https://www.cnblogs.com/acha/p/9042984.html
• https://blog.csdn.net/a_crazy_czy/article/details/73611366
• https://en.wikipedia.org/wiki/Tutte_polynomial#Reliability_polynomial
• https://en.wikipedia.org/wiki/Lindstr%C3%B6m%E2%80%93Gessel%E2%80%93Viennot_lemma