算法总结

Tarjan

目的

求 $\operatorname{SCC}$（强连通分量）

本处定义

• $\operatorname{SCC}$：一个点集，在其中的点都可以通过边集中的边互相到达。

• 时间戳：针对每一个点，以其在 $\operatorname{DFS}$ 序中的次序按自然数顺序给定的值，常用 $\operatorname{dfn}$ 表示。

• 追溯值：在不经过之前的树边的情况下，能够到达的时间戳最小的点（有点抽象，不太能理解，大概是这个意思吧），常用 $\operatorname{low}$ 表示。

• 缩点：将一些 $\operatorname{SCC}$ 使用一个点进行等效替代的方法。

• 割点：如果把某点以及它相连的边删除后，图的 $\operatorname{SCC}$ 增加了，那么这个点就是这个图的割点。

• 割边：如果把某边删除后，图的 $\operatorname{SCC}$ 增加了，那么这条边就是这个图的割边。

• 点双（点双连通分量）：将图中的割点除去后，剩下的连通分量再加上原来它通过直接边连接的割点（一个割点可以同时在多个点双连通分量内）。

• 边双（边双连通分量）：将图中的边集除去割边后，剩下的连通分量。

• 一些代码中的定义：

void tarjan(int x){
	//进入节点 x 时
	加戳
	for(枚举儿子){
		if(未访问){
			递归
			//回溯时
			记录
		}
		else if(栈中)
			//栈中处理
	}
	//返回时
}

判定方法（简便求法）

时间戳

直接在加戳时加盖就行了。

追溯值

在回溯时用儿子的 $\operatorname{low}$ 值更新，并在栈中处理时使用它的 $\operatorname{dfn}$ 值更新。

缩点

方法多样，可用 namespace 法，将 $\operatorname{SCC}$ 内的多个信息合并后，在一个新的 namespace 内重新建图 ，方便好用。

割点

对于某非根节点 $x$，若 $\forall y \isin V_{x'son},\operatorname{low}_{y} < \operatorname{dfn}_{x}$ 则 $x$ 非割点。

割边

可以使用类似于割点的方法，但是不同的是得加一条特判，不能走回头路，还有既然不能走回头路了，那等于的情况也就不合法了，所以改为若 $\forall y \isin V_{x'son},\operatorname{low}_{y} \le \operatorname{dfn}_{x}$ 则 $x$ 非割点

边双连通分量

相当于割边和割点结合起来，详情见代码

点双连通分量

要处理的有点多，首先所有的数组啊，栈啊都要开，其次统计答案的位置改为了回溯时，因为这改了，所以也需要特判一下只有一个点的独立点的情况。

代码

时间戳+追溯值

#include<bits/stdc++.h>
using namespace std;
struct Edge{
	int v,nxt;
}edge[50000+10];
int head[10000+10],idx;
void add(int u,int v){
	edge[++idx]={v,head[u]};
	head[u]=idx;
}
int n,m,scc[10000+10],dfn[10000+10],low[10000+10],cnt,idk;
stack<int>stk;
void tarjan(int x){
	dfn[x]=low[x]=++idk;
	stk.push(x);
	for(int i=head[x];i;i=edge[i].nxt){
		if(!dfn[edge[i].v])
			tarjan(edge[i].v),
			low[x]=min(low[x],low[edge[i].v]);
		else if(!scc[edge[i].v])
			low[x]=min(low[x],dfn[edge[i].v]);
	}
	if(low[x]==dfn[x]){
		cnt++;
		while(stk.size()){
			int now=stk.top();stk.pop();
			scc[now]=cnt;
			if(now==x) break;
		}
	}
}
int cur[10000+10];
int main(){
	ios_base::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1,u,v;i<=m;++i){
		cin>>u>>v;
		add(u,v);
	}
	for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i);
	int anss=0;
	for(int i=1;i<=n;++i)
		++cur[scc[i]];
	for(int i=1;i<=cnt;++i)
		if(cur[i]>1) anss++;
	cout<<anss<<endl;
	return 0;
}

例题

缩点

#include<bits/stdc++.h>
using namespace std;
struct Edge{
	int u,v,nxt;
}edge[100000+10];
int head[10000+10],idx,a[10000+10];
void add(int u,int v){
	edge[++idx]={u,v,head[u]};
	head[u]=idx;
}
int n,m,scc[10000+10],dfn[10000+10],low[10000+10],cnt,idk;
stack<int>stk;
void tarjan(int x){
	dfn[x]=low[x]=++idk;
	stk.push(x);
	for(int i=head[x];i;i=edge[i].nxt){
		if(!dfn[edge[i].v])
			tarjan(edge[i].v),
			low[x]=min(low[x],low[edge[i].v]);
		else if(!scc[edge[i].v])
			low[x]=min(low[x],dfn[edge[i].v]);
	}
	if(low[x]==dfn[x]){
		cnt++;
		while(stk.size()){
			int now=stk.top();stk.pop();
			scc[now]=cnt;
			if(now==x) break;
		}
	}
}
int cur[10000+10];
namespace SCCed{
	struct Edge{
		int v,nxt;
	}edge[100000+10];
	int head[10000+10],idx,fa[10000+10];
	void add(int u,int v){
		edge[++idx]={v,head[u]};
		head[u]=idx;
	}
	int n,l[100000+10];
	void main(){
		queue<int>q;
		n=::cnt;
		
		for(int i=1;i<=n;++i){
			if(fa[i]==0) q.push(i);
			l[i]=::cur[i];
		}
		
		while(!q.empty()){
			int now=q.front();q.pop(); /*cerr<<" "<<now<<" "<<l[now]<<endl;*/
			for(int i=head[now];i;i=edge[i].nxt){
				l[edge[i].v]=max(l[now]+::cur[edge[i].v],l[edge[i].v]);
				--fa[edge[i].v];
				if(fa[edge[i].v]==0) q.push(edge[i].v);
			}
		}
		
		int anss=0;
		
		for(int i=1;i<=n;++i) anss=max(anss,l[i]);
		
		cout<<anss<<endl;
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=n;++i) cin>>a[i];
	for(int i=1,u,v;i<=m;++i){
		cin>>u>>v;
		add(u,v);
	}
	for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i);
	for(int i=1;i<=n;++i) cur[scc[i]]+=a[i];
	for(int i=1;i<=idx;++i)
		if(scc[edge[i].u]^scc[edge[i].v])
			SCCed::add(scc[edge[i].v],scc[edge[i].u]),SCCed::fa[scc[edge[i].u]]++;
	SCCed::main();
	return 0;
}

例题

割点

#include<bits/stdc++.h>
using namespace std;
struct Edge{
	int u,v,nxt;
}edge[1000000+10];
int head[100000+10],idx,a[100000+10];
void add(int u,int v){
	edge[++idx]={u,v,head[u]};
	head[u]=idx;
}
int n,m,scc[100000+10],dfn[100000+10],low[100000+10],cnt,idk,root;
vector<int>ans;
void tarjan(int x){
	dfn[x]=low[x]=++idk;
	int chd=0;
	for(int i=head[x];i;i=edge[i].nxt){
		if(!dfn[edge[i].v]){
			tarjan(edge[i].v),
			low[x]=min(low[x],low[edge[i].v]);
			if(low[edge[i].v]>=dfn[x]){
				chd++;
				if(x!=root||chd>1)
					ans.push_back(x);
			} 
		}
		else
			low[x]=min(low[x],dfn[edge[i].v]);
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1,u,v;i<=m;++i){
		cin>>u>>v;
		add(u,v);add(v,u);
	}
	for(int i=1;i<=n;++i) if(!dfn[i]) root=i,tarjan(i);
//	for(int i=1;i<=n;++i) cout<<dfn[i]<<','<<low[i]<<' ';cout<<endl;
//	cout<<ans.size()<<endl;
//	for(int i=1;i<=ans.size();++i) cout<<ans[i-1]<<' ';
//	cout<<endl;
	sort(ans.begin(),ans.end());
	ans.erase(unique(ans.begin(),ans.end()),ans.end());
	cout<<ans.size()<<endl;
	for(int i=1;i<=ans.size();++i) cout<<ans[i-1]<<' ';
	return 0;
}

例题

割边

#include<bits/stdc++.h>
using namespace std;
struct Edge{
	int u,v,nxt;
}edge[100000+10];
int head[10000+10],idx=1,a[10000+10];
void add(int u,int v){
	edge[++idx]={u,v,head[u]};
	head[u]=idx;
}
int n,m,scc[10000+10],dfn[10000+10],low[10000+10],cnt,idk;
struct EDGE{
	int u,v;
	EDGE():u(0),v(0){}
	EDGE(int u1,int v1){if(u1>v1)swap(u1,v1);u=u1;v=v1;}
	friend bool operator==(const EDGE&a,const EDGE&b){
		return a.u==b.u&&a.v==b.v;
	}
	friend bool operator<(const EDGE&a,const EDGE&b){
		return a.u==b.u?a.v<b.v:a.u<b.u;
	}
};
vector<EDGE>ans;
void tarjan(int x,int in){
	dfn[x]=low[x]=++idk;
	for(int i=head[x];i;i=edge[i].nxt){
		if(!dfn[edge[i].v]){
			tarjan(edge[i].v,i),
			low[x]=min(low[x],low[edge[i].v]);
			if(low[edge[i].v]>dfn[x]){
				ans.push_back(EDGE(x,edge[i].v));
			} 
		}
		else if(in^1^i)
			low[x]=min(low[x],dfn[edge[i].v]);
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1,u,v;i<=m;++i){
		cin>>u>>v;
		add(u,v);add(v,u);
	}
	for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i,0);
//	for(int i=1;i<=n;++i) cout<<dfn[i]<<','<<low[i]<<' ';cout<<endl;
//	cout<<ans.size()<<endl;
//	for(int i=1;i<=ans.size();++i) cout<<ans[i-1]<<' ';
//	cout<<endl;
	sort(ans.begin(),ans.end());
	ans.erase(unique(ans.begin(),ans.end()),ans.end());
	for(int i=1;i<=ans.size();++i) cout<<ans[i-1].u<<' '<<ans[i-1].v<<endl;
	return 0;
}

例题

边双连通分量

#include<bits/stdc++.h>
using namespace std;
struct Edge{
	int u,v,nxt;
}edge[8000000+10];
int head[5000000+10],idx=1,a[5000000+10];
void add(int u,int v){
	edge[++idx]={u,v,head[u]};
	head[u]=idx;
}
int n,m,scc[5000000+10],dfn[5000000+10],low[5000000+10],cnt,idk;
stack<int>stk;
vector<int>edcc[5000000+10];
void tarjan(int x,int in){
	dfn[x]=low[x]=++idk;stk.push(x);
	for(int i=head[x];i;i=edge[i].nxt){
		if(!dfn[edge[i].v]){
			tarjan(edge[i].v,i),
			low[x]=min(low[x],low[edge[i].v]);
		}
		else if(in^1^i)
			low[x]=min(low[x],dfn[edge[i].v]);
	}
	if(dfn[x]==low[x]){
		++cnt;
		while(stk.size()){
			int now=stk.top();stk.pop();
			edcc[cnt].push_back(now);
			if(now==x) break;
		}
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1,u,v;i<=m;++i){
		cin>>u>>v;
		add(u,v);add(v,u);
	}
	for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i,0);
	cout<<cnt<<endl;
	for(int i=1;i<=cnt;++i){
		cout<<edcc[i].size()<<' ';
		for(int j=1;j<=edcc[i].size();++j)
			cout<<edcc[i][j-1]<<' ';
		cout<<endl;
	}
	return 0;
}

例题

点双连通分量

#include<bits/stdc++.h>
using namespace std;
struct Edge{
	int u,v,nxt;
}edge[2000000+10];
int head[500000+10],idx,a[100000+10];
void add(int u,int v){
	edge[++idx]={u,v,head[u]};
	head[u]=idx;
}
int n,m,dfn[500000+10],low[500000+10],idk,root;
stack<int>stk;
vector<vector<int>>vdcc;
bool pt[500000+10];
void tarjan(int x){
	dfn[x]=low[x]=++idk;
	stk.push(x);
	int chd=0;
	for(int i=head[x];i;i=edge[i].nxt){
		int v(edge[i].v);
		if(!dfn[v]){
			tarjan(v);
			low[x]=min(low[x],low[v]);
			if(low[v]>=dfn[x]){
				chd++;
				if((x^root)||chd>1)
					pt[x]=1;
				vdcc.push_back(vector<int>());
				while(stk.size()){
					int now=stk.top();stk.pop();
					vdcc.back().push_back(now);
					if(now==v) break;
				}
				vdcc.back().push_back(x);
			}
		}
		else
			low[x]=min(low[x],dfn[v]);
	}
	if(!chd&&x==root){
		vdcc.push_back(vector<int>());
		vdcc.back().push_back(x);
		return;
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1,u,v;i<=m;++i){
		cin>>u>>v;
		add(u,v);add(v,u);
	}
	for(int i=1;i<=n;++i)
		if(!dfn[i])
			root=i,tarjan(i);
	cout<<vdcc.size()<<endl;
	for(vector<int>&now:vdcc){
		cout<<now.size()<<' ';
		for(int&qwq:now)
			cout<<qwq<<' ';
		cout<<endl;
	}
	return 0;
}

例题

二分图

一些基本概念

• 二分图：一张图$G=\{V,E\}$，若其中的点集 $V$ 可以使 $\exists V_1,V_2,V_1 \cup V_2 = V ,V_1 \cap V_2 = \phi,\forall e \isin E,{e_u,e_v}\not \isin V_1,{e_u,e_v}\not \isin V_2 $ 成立，则称之为二分图。

• 最大匹配子图：一张二分图，在其中选出若干条边，使得这些边所连接的点不重合，则最多的边集合与它们各自的端点的集合便为最大匹配子图。

实现

二分图

可以使用染色法：假定一个节点属于左集，则有直接边与之相连的点属于右集，再以此类推，可得所有点分属哪个集合，若矛盾，则给定图非二分图。

最大匹配子图

先枚举每一个左集中的点，穷举每一条与之相连的边，查看右集中与之相连的点是否已被其他点占据，若没有，则选边，否则让那个点查看是否仍有其他选择，若仍被其他点占据，则重复此过程，看看最后能否空出此点。

核心思想：前面来的给后面让，前面的让不了就不让，一直让不了就舍弃。

代码

二分图（染色）

#include<bits/stdc++.h>
using namespace std;
struct Edge{
	int v,w,nxt;
}edge[200000+10];
int head[20000+10],idx;
void add(int u,int v,int w){
	edge[++idx]={v,w,head[u]};
	head[u]=idx;
}
short color[20000+10];
bool chk(int mid,int s){
	queue<pair<int,bool>>q;
	q.emplace(s,false);
	while(!q.empty()){
		pair<int,bool>now=q.front();
		q.pop();
		if(color[now.first]==-1){
			color[now.first]=now.second;
			for(int i=head[now.first];i;i=edge[i].nxt){
				if(edge[i].w>mid) q.emplace(edge[i].v,!now.second);
			}
		}
		else if(color[now.first]!=now.second) return 0;
	}
	return 1;
}
int n,m,u,v,w,l,r,mid;
bool check(int mid){
	memset(color,-1,sizeof color);
	for(int i=1;i<=n;++i)
		if(color[i]==-1)
			if(!chk(mid,i)) return 0;
	return 1;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=m;++i) cin>>u>>v>>w,add(u,v,w),add(v,u,w),r=max(r,w);
	while(l<r){
		mid=l+r>>1;
		if(check(mid)) r=mid;
		else l=mid+1;
	}
	cout<<l<<endl;
	return 0;
}

例题

二分图最大匹配

#include<bits/stdc++.h>
using namespace std;
int n,m,e,u,v,belong[500+10];
vector<int>may[500+10];
bool now[500+10];
bool chg(int x){
	if(now[x]) return 0;
	now[x]=1;
	for(int i:may[x]){
		if(!belong[i]){
			belong[i]=x;
			return 1;
		}
		if(chg(belong[i])){
			belong[i]=x;
			return 1;
		}
	}
	return 0;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin>>n>>m>>e;
	for(int i=1;i<=e;++i){
		cin>>u>>v;
		may[u].push_back(v);
	}
	for(int i=1;i<=n;++i){
		sort(may[i].begin(),may[i].end());
		may[i].erase(unique(may[i].begin(),may[i].end()),may[i].end());
	}
	int ans=0;
	for(int i=1;i<=n;++i){
		memset(now,0,sizeof now);
		if(chg(i)) ans++;
	}
	cout<<ans<<endl;
	return 0;
}

例题

树链剖分

一些基本概念

• 重儿子：一个节点的所有儿子中以它为根的子树最大的那个儿子是重儿子。
• 轻儿子：一个节点不是重儿子就是轻儿子。
• 重边：连接一个节点和它的重儿子的边。
• 轻边：一条边不是重边就是轻边。
• 重链：一堆相连的重边组成的一条路径。

求法

重儿子、轻儿子、重边、轻边、重链

就按照定义求。

例

重链剖分求 LCA

对于两个点，我们让所在重链深度最小的点深度更小的点跳跃到其所在重链深度最小的点的父节点。

重复进行此操作，直到其处于同一条重链。

重链剖分求树上路径操作

参考例题，可以将所有点按 $\operatorname{DFS}$ 序重新赋值点编号，对于具体的点优先访问其重儿子。

这样就让一条重链上的点编号相邻，子树上连续了，然后线段树，启动。

代码

LCA

#include<bits/stdc++.h>
using namespace std;
struct Edge {
	int v, nxt;
}edge[1000000 + 10];
int head[500000 + 10], idx;
void add(int u, int v) {
	edge[++idx] = { v,head[u] };
	head[u] = idx;
}
int n, m, s, a, b, hson[500000 + 10], siz[500000 + 10], fa[500000 + 10], belong[500000 + 10], dep[500000 + 10];
void dfs1(int x, int f) {
	fa[x] = f; dep[x] = dep[f] + 1;
	for (int i = head[x]; i; i = edge[i].nxt) {
		if (edge[i].v == f) continue;
		dfs1(edge[i].v, x);
		siz[x] += siz[edge[i].v];
		if (siz[edge[i].v] > siz[hson[x]]) hson[x] = edge[i].v;
	}
	siz[x]++;
}
void dfs2(int x, int idk) {
	belong[x] = idk;
	if (hson[x]) dfs2(hson[x], idk);
	for (int i = head[x]; i; i = edge[i].nxt) {
		if (edge[i].v == fa[x] || edge[i].v == hson[x]) continue;
		dfs2(edge[i].v, edge[i].v);
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin >> n >> m >> s;
	for (int i = 1; i < n; ++i) cin >> a >> b, add(a, b), add(b, a);
	dfs1(s, 0);
	dfs2(s, s);
// 	for (int i = 1; i <= n; ++i) cout << belong[i] << ' '; cout << endl;
	while (m--) {
		cin >> a >> b;
		while (belong[a] ^ belong[b]) {
			if (dep[belong[a]] < dep[belong[b]]) swap(a, b);
			a = fa[belong[a]];
		}
		if (dep[a] < dep[b]) cout << a << endl;
		else cout << b << endl;
	}
	return 0;
}
/*
8 1 6
6 2
1 7
4 8
3 5
1 8
2 8
2 5
4 5
*/

可持久化

定义

• 可持久化：可以使数据结构访问过去版本的一种奇技淫巧思想。

实现

多开一些节点，但是在两颗树间的相同节点共用，这样一个版本更新只需要 $\log_2n$ 的空间复杂度了。

代码

出自题单

LCT