省选-图论杂项

1. （前置知识）Boruvka
2. Kruskal 重构树
3. 分层图选讲（包括斯坦纳树）
4. 竞赛图 .5. 杂项：树哈希，弦图，支配树

Boruvka

对每个当前连通块，找它和别的连通块之间的边中，边权最小的。

然后把所有找到的边都加入最小生成树。不会成环。

复杂度 $O(n\log n)$。

Kruskal 重构树

每一次加边会合并两个集合，我们可以新建一个点，点权为加入边的边权。

同时将两个集合的根节点分别设为新建点的左儿子和右儿子，将新建点设为根。

在进行 $n-1$ 轮之后我们得到了一棵恰有 $n$ 个叶子的二叉树，同时每个非叶子节点恰好有两个儿子，这就是 Kruskal 重构树。

是不是太特殊了，来个更特殊的。

性质：原图中两个点之间的所有简单路径上最大边权的最小值 = 最小生成树上两个点之间的简单路径上的最大值 = Kruskal 重构树上两点之间的 LCA 的权值。

P4768 [NOI2018] 归程

P4768 [NOI2018] 归程。

这道题问的是路径的最小和。

我们发现前一段的海拔大于当天的水位线，这个限制我们可以用 Kruskal 重构树 去解决一下。我们需要找到所有能到达的点，也就是重构树上的一个子树。

然后答案就是从可以到达的点集中距离 $1$ 最近的。

利用性质：边的边权单调。

P13548 [OOI 2022] Air Reform

P13548 [OOI 2022] Air Reform。

简单总结一下，对于瓶颈路问题，最小生成树可以替代 Kruskal 重构树，但是“只能走边权 $\le k$”这种问题必须要用。

CF1583H Omkar and Tours

CF1583H Omkar and Tours。

使一个节点和另一个节点 LCA 的 dfs 序最小，另一个节点选 dfn 最小或最大的节点。

分层图

P4568 [JLOI2011] 飞行路线

P4568 [JLOI2011] 飞行路线。

每走一层就是用了一次免费搭乘飞机的机会。

P3831 [SHOI2012] 回家的路

P3831 [SHOI2012] 回家的路。

分层，横纵各是一层，然后层间就是换乘站。特殊的，起点和终点换乘不需要时间。

P9370 [APIO2023] 赛博乐园 / cyberland

P9370 [APIO2023] 赛博乐园 / cyberland。

差不多，就是用一次就走一层。

这道题比较独特的就是清零了就相当于可以从这个点重新开始。

代码不好写，vector 建图还被卡常了。

斯坦纳树

给定一个图，需要求一个最小子图，包含给定的点，并且联通。给定的点很少，需要状压。

P6192 【模板】最小斯坦纳树

P6192 【模板】最小斯坦纳树。

考虑状压 $\text {dp}$，设 $f_{i,S}$ 表示以 $i$ 为根的答案中包含集合 $S$ 中所有点的最小边权值和。

$f(i,S)\leftarrow \min(f(i,S),f(i,T)+f(i,S-T))$

$f(i,S)\leftarrow \min(f(i,S),f(j,S)+w(j,i))$

我们的两个转移分别覆盖了加边和加点两种情况，所以完整。

时间复杂度 $O(n\times 3^k+nm\times 2^k)$。

P4294 [WC2008] 游览计划

P4294 [WC2008] 游览计划。

这道题求的是点权，所以需要改一下。

P3264 [JLOI2015] 管道连接

P3264 [JLOI2015] 管道连接。

每个情报站有一个特定的频道，需要 使得任意相同频道的情报站之间都建立通道连接。

这道题是求完斯坦纳树的 dp 之后再进行一次 dp。

树哈希

P5043 【模板】树同构 / [BJOI2015] 树的同构

P5043 【模板】树同构 / [BJOI2015] 树的同构。

一种好写的树哈希。

这道题找到重心，然后计算哈希就行了。

P4323 [JSOI2016] 独特的树叶

P4323 [JSOI2016] 独特的树叶。

刚才的哈希可能稍显复杂，看到题解中还有这种：

$f(x)=\sum\limits_{y\in Son_x}f(y)\times\text{P}(Size(y))\mod M$

用...质数表。

P8499 [NOI2022] 挑战 NPC Ⅱ

P8499 [NOI2022] 挑战 NPC Ⅱ。

弦图

弦图：没有长度 $> 3$ 的纯环的图。

性质：区间图是弦图。看到最大独立集（团）、染色数等问题，可以猜这是一个弦图。

完美消除序列

定义

单纯点：邻集加上自己是团。

完美消除序列：$v_i$ 在 $v_i , v_{i+1}, … , v_n$ 的导出子图内是单纯点。

是弦图 等价于 有完美消除序列。

线段图是弦图。

最大势算法

用来求完美消除序列的，$O(n)$ 但是可以 $O(n\log n)$ 写着更方便。

从 $n$ 到 $1$ 给点标号（即倒序填完美消除序列），每次选择最多邻居是 已标号的点的点标号。

然后判断这个是不是就行了。

性质

Lemma 1：

团数 $\omega(G)\le \chi(G)$ 色数

证明：考虑单独对最大团的导出子图（就是选取一些点，然后连边原图有的新图也要有）进行染色，至少需要 $\omega(G)$ 种颜色。

P14506 【模板】弦图

P14506 【模板】弦图。

这道题直接用最大势算法判断。

然后写法的话就是对于每一个点，看它的后继与剩余的相邻的点是否有连边就行了，可以理解为具有传递性吧，就是其它情况前面的节点已经判断过了。

• 最大团大小：对每个点，它加上它后面邻居的个数，取最大值。因为每个点与后面邻居构成团。

• 色数：因为色数大于等于最大团的大小，然后构造等于，一种构造方法：按完美消除序列从后往前贪心染色：每个点的后继邻居构成一个团，最多用 $ω−1$ 种颜色，因此总能从 $1∼ω$ 中选到可用颜色，从而 $χ≤ω$。

• 最大独立集：贪心：按完美消除序列从前到后，如果一个点没有被已选独立集中的点相邻，就选它，并标记其邻居不可选。简单理解一下，就是当前点和它后面连边的都在最大团里面，选了一定没有当前优。

#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int>e[200010],b[200010],l[200010];
int vis[200010],xl[200010],p[200010],h[200010],c[200010];

bool check(){
	for(int i=1;i<=n;i++){
		for(int v:e[i])if(p[i]<p[v])l[i].push_back(v);
	}
	for(int i=1;i<=n;i++){
		if(l[i].size()<2)continue;
		int u=l[i][0];
		for(int j=1;j<l[i].size();j++){
			int v=l[i][j];
			auto it=lower_bound(e[u].begin(),e[u].end(),v);
			if(*it!=v)return 0;
		}
	}
	return 1;
}
void solve(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)e[i].clear(),b[i].clear(),l[i].clear();
	for(int i=1;i<=n;i++)vis[i]=h[i]=c[i]=0;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	for(int i=1;i<=n;i++)sort(e[i].begin(),e[i].end());
	for(int i=1;i<=n;i++)b[0].push_back(i);
	int now=0;
	for(int i=n;i>=1;i--){
		int x=-1;
		while(1){
			while(!b[now].empty()){
				int v=b[now].back();
				b[now].pop_back();
				if(!vis[v]){
					x=v;
					break;
				}
			}
			if(x!=-1)break;
			now--;
		}
		vis[x]=1,xl[i]=x,p[x]=i;
		for(int v:e[x]){
			if(vis[v])continue;
			h[v]++;
			b[h[v]].push_back(v);
			if(h[v]>now)now=h[v];
		}
	}
	if(!check()){
		cout<<"No"<<endl;
		return;
	}
	cout<<"Yes"<<endl;
	for(int i=1;i<=n;i++)cout<<xl[i]<<' ';
	cout<<endl;
	int ans=0;
	for(int i=1;i<=n;i++){
		int res=1;
		for(int v:e[xl[i]])res+=(p[v]>p[xl[i]]);
		ans=max(ans,res);
	}
	cout<<ans<<' '<<ans<<' ';
	ans=0;
	for(int i=1;i<=n;i++){
		int u=xl[i],pd=1;
		for(int v:e[u]){
			if(c[v]){
				pd=0;
				break;
			}
		}
		if(pd){
			c[u]=1;
			ans++;
		}
	}
	cout<<ans<<endl;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int T;
	cin>>T;
	while(T--){
		solve();
	}
	
	return 0;
}

支配树

支配树：给定有向图 $G$ 和根 $r$，支配树满足 $x$ 的子树恰好是那些删去 $x$ 后 $r$ 不可达的点。

DAG 上的支配树：P2597 [ZJOI2012] 灾难

P2597 [ZJOI2012] 灾难。

在 DAG 上求支配树然后求节点 size 即可。

例题：P7520 [省选联考 2021 A 卷] 支配

P7520 [省选联考 2021 A 卷] 支配。

普通支配树：P5180 【模板】支配树

P5180 【模板】支配树。

竞赛图

竞赛图：$n$ 个点的有向图，任意两个点之间恰有一条有向边。

性质

缩点成链

竞赛图缩点后，所有 SCC 构成的东西呈链状，因此竞赛图上可以快速判断可达性。

链上的每个前后缀都是独立的“子竞赛图”。

关于哈密顿路径

存在一条哈密顿路径

考虑进行插点，插点进去。

对于原来的路径中，找出相对于新的点的出边，然后路径上下一个点是这个点的入边的位置插进去就行了。如果只有入/出就放开头/结尾。

竞赛图任意一个 SCC 存在一条哈密顿回路

同样是插点进去。

对于原来的路径中，先构造回路。

对于新的点，一定有入边和出边（不可能只有出边/入边连接这个点），那直接把这两个点之间的路径加上这个点就行了。

关于环的性质

• 竞赛图若有环一定存在三元环。

• 竞赛图的 $k>=3$ 个点的 SCC 中一定存在 $[3,k]$ 元环。

• 有 $\dbinom{n}{3}-\sum\limits_{i=1}^n \dbinom{out_{i}}{2}$ 个三元环（总-三个点中有一个点出度为 $2$ 的情况）。

其它

• 若 $x$ 的出度大于 $y$ 的出度，则 $x$ 可以到达 $y$。

CF1498E Two Houses

CF1498E Two Houses。

若 $x$ 的出度大于 $y$ 的出度，则 $x$ 可以到达 $y$。

兰道定理

这个讲的比较详细。

我们定义比分序列为将每个点的出度 $s_{i}$ 从小到大排序的序列。

那么若满足 $\sum\limits_{i=1}^k s_{i}\ge \dbinom{k}{2}$ 且当 $k=n$ 时取等（即 $\sum\limits s=\dbinom{n}{2}$），则一定能够造出一种竞赛图，反之不能。

必要性显然，考虑充分性证明，我们构造初始图，对于 $j<i$ 则 $i\to j$ 连边，设此时比分序列为 $a$，这个序列显然在上述条件能够取到等号。保持 $\sum\limits_{i=1}^k a_{i}\le \sum\limits_{i=1}^k s_{i}$，不断调整图直到 $a=s$。

充分性怎么构造？

CF850D Tournament Construction

CF850D Tournament Construction。

兰道定理求强连通分量

分界点：

每个点出度为 $s_i$。