图论

floyd算法

最短路

floyd算法适用于多源最短路

cpp
1
2
3
4
5
6
7
for(int k=1;k<=n;k++){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
		}
	}	
}

值得一提的是，如果有一条边的边权更新，那么会出现下面两种情况：

1. 边权变小，那么只需要以边上两端点为中继点跑floyd（因为如果存在两点之间的最短路变小了，那么这个最短路一定过了这条边）

2. 边权变大，需要重新跑整个的floyd（因为原来的最短路被破坏）

传递闭包

使用floyd可以判断两点是否连通（主要是单向连通，可能会有A能到B，B不能到A的情况）（这种单向连通关系为不等式提供了很好的条件）

这种情况下的$dis[][]$的含义发生变化，$dis[][]=1$说明可以到达，$dis[][]=0$ 说明不能到达。据此我们有

cpp
1
2
3
4
5
6
7
for(int k=1;k<=n;k++){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			dis[i][j]=max(dis[i][j],dis[i][k]&&dis[k][j]);
		}
	}	
}

例题：AcWing 343

无向图最小环

求权值

枚举中间点k。此时前k-1的点之间的最短路关系已经求出，我们可以有环$dis[i][j]+a[k][i]+a[k][j]$

枚举完环再去求最短路

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
long long ans=0x3f3f3f3f;
for(int k=1;k<=n;k++){
	for(int i=1;i<k;i++){
		for(int j=i+1;j<k;j++){
			ans=min(ans,(long long)dis[i][j]+a[i][k]+a[k][j]);
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			dis[i][j]=dis[j][i]=min(dis[i][j],dis[i][k]+dis[k][j]);
		}
	}
}

有两个注意点

1. 由于最后的ans是三个变量相加，可能有爆int的风险，所以ans变量需要是long long类型。不能直接 #define int long long 因为三个long long相加会爆long long

2. 存图的时候需要注意，有可能有重边！

求路径

对于每一个最短路，我们都记录这两个点之间的最短路是由哪个中继点中继来的。然后dfs输出路径

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int mid[101][101];//记录两点之间最短路是哪个中继点中继过来的
vector<int> path;//最后要输出的答案
void dfs(int a,int b){
	int k=mid[a][b];
	if(k==0) return; 
	dfs(a,k);
	path.push_back(k);
	dfs(k,b);
}
inline void push(int i,int j,int k){
	path.clear();
	path.push_back(k);
	path.push_back(i);
	dfs(i,j);
	path.push_back(j);
}

floyd部分类似

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
long long ans=0x3f3f3f3f;
for(int k=1;k<=n;k++){
	for(int i=1;i<k;i++){
		for(int j=i+1;j<k;j++){
			if(ans>(long long)dis[i][j]+a[i][k]+a[k][j]){
				ans=dis[i][j]+a[i][k]+a[k][j];
				push(i,j,k);
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(dis[i][j]>dis[i][k]+dis[k][j]){
				dis[i][j]=dis[j][i]=dis[i][k]+dis[k][j];
				mid[j][i]=mid[i][j]=k;
			}
		}
	}
}

dijkstra算法

dijkstra算法求最短路只适用于边权都为正数的情况。有负边权，则需要使用spfa算法

和prim算法类似，都需要vis数组来记录点是否进入过队列

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
typedef pair<int,int> pii;
int dis[100005];
int vis[100005];
void dijkstra(int x){
	memset(dis,0x3f,sizeof(dis));
	dis[x]=0;
	priority_queue<pii,vector<pii>,greater<pii> > q;
	q.push(make_pair(0,x));
	while(!q.empty()){
		int now=q.top().second;q.pop();
		if(vis[now]) continue;
		vis[now]=true;
		for(int i=head[now];i;i=edge[i].next){
			int to=edge[i].to;
			int w=edge[i].w;
			if(dis[to]>dis[now]+w){
				dis[to]=dis[now]+w;
				if(!vis[to]){
					q.push(make_pair(dis[to],to));
				}
			}
		}
	}
}

最短路计数

设 $num[x]$ 表示以点x结尾的最短路的数量
初始化有 $num[s]=1$

松弛成功时，有 $num[to]=num[now]$
$dis[to]=dis[now]+w$时，有 $num[to]+=num[now]$

分层图最短路

如果最短路过程中涉及到了状态转移（类似dp那种），则需要用到分层图最短路

例如求源点到其他点的最短路，其中可以有 $k$ 条边的长度视为 $0$。

$dis[x][k]$ 表示到 $x$ 点，已经用了 $k$ 次无视长度的机会

注意 vis 数组也要附加一维状态

初始化 $dis[s][0]=0$

在堆中维护的元素需要有三个属性：最短路长度，节点编号，用了多少次无视长度的机会

松弛时，存在两个状态转移，使用无视长度的机会还是不使用

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int vis[10004][11],dis[10004][11];
void dijkstra(){
	memset(dis,0x3f,sizeof(dis));
	dis[s][0]=0;
	priority_queue<pii> q;
	q.push(pii(s,0,0));
	while(!q.empty()){
		pii tmp=q.top();
		q.pop();
		int now=tmp.u;
		int cnt=tmp.cnt;
		if(vis[now][cnt]) continue;
		vis[now][cnt]=true;
		for(int i=head[now];i;i=edge[i].next){
			int to=edge[i].to;
			int w=edge[i].w;
			if(cnt<k&&dis[now][cnt]<dis[to][cnt+1]){
				dis[to][cnt+1]=dis[now][cnt];
				q.push(pii(to,dis[to][cnt+1],cnt+1));
			}
			if(dis[now][cnt]+w<dis[to][cnt]){
				dis[to][cnt]=dis[now][cnt]+w;
				q.push(pii(to,dis[to][cnt],cnt));
			}
		}
	}
}  

次短路

设 $dis1[]$ 为到当前点的最短路，$dis2[]$ 为到当前点的次短路
对于边 $(u,v,w)$ 转移的时候就有：

如果 $dis1[u]+w<dis1[v]$ 则 $dis1[v]=dis1[u]+w$

如果 $dis1[v]<dis1[u]+w$ （注意不能取等，否则最短路和次短路长度可能相同） 但 $dis1[u]+w<dis2[v]$ 则 $dis2[v]=dis1[u]+w$

如果 $dis2[u]+w<dis2[v]$ 则 $dis2[v]=dis2[u]+w$（值得注意的是，如果条件二触发了，则条件三一定不会触发）

上述三个条件任意一个触发，都让v入队。在优先队列中，按 $dis1[]$ 作为关键字进行比较

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool flag=false;
if(dis1[now]+w<dis1[to]){
	dis1[to]=dis1[now]+w;
	flag=true;
}
if(dis1[now]+w>dis1[to]&&dis1[now]+w<dis2[to]){
	dis2[to]=dis1[now]+w;
	flag=true;
}
if(dis2[now]+w<dis2[to]){
	dis2[to]=dis2[now]+w;
	flag=true;
}
if(flag){
	q.push(pii(dis1[to],to));
}

注意与树形dp求树的直径做区分，次短路是严格小于的，因此不能取等，而树的直径的dis2是可以和dis1相等的

最短路图

在图上，从s到任意一点的路径长度都为这个点的最短路。对于不同的源点可以求出不同的最短路图。

无向图

无向图最短路图为最短路树。

事实上，我们仍然可以对无向图求最短路图。只需要枚举每个点，然后遍历当前点所有的边，检查边是否满足$dis[u]+w=dis[v]$。再保证每个点只有一个入度即可。这样求出的最短路树和字典序有关。

最短路树可能有多个，一般我们只需要获得任意一个用来研究。

我们可以通过记录某个节点和其父节点是由哪个边连起来的，这样来求最短路树

cpp
1
2
3
4
5
            if(dis[now]+w<dis[to]){
				dis[to]=dis[now]+w;
				pre[to]=i;
				q.push(pii(dis[to],to));
			}

有向图

有向图最短路图是一个DAG。 首先使用dijkstra算法求出$dis[]$，然后遍历每一条边。对于一条边$(u,v,w)$，如果满足$dis[u]+w=dis[v]$，那么这条边在最短路图上。

dijkstra部分略

cpp
1
2
3
4
5
6
7
8
9
10
11
int is[3003];
int in[3003];
for(int i=1;i<=m;i++){
	int u=edge[i].from;
	int v=edge[i].to;
	int w=edge[i].w;
	if(dis[u]+w==dis[v]){
		is[i]=true;
      		in[v]++;
	}
}

使用$is[]$，就可以无需重新建图实现在图上拓扑排序，只需枚举到一个边时判断其is值，如果为false则忽略即可。

一个应用

在DAG上求边数经过次数

利用最短路图，可以实现在DAG上求有多少个最短路经过了这个边

注意：如果没有说明源点，那么你需要做多次下面的算法

需要两次拓扑排序：

第一次求从源点有多少条路径经过一个点。初始化$cnt1[s]=1$，然后拓扑排序，对于边$(u,v)$，有转移方程$cnt1[v]+=cnt1[u]$

第二次求从一个点出去会经过多少点。需要对最短路图建反图。在反图上，初始化$cnt2[任意点]=1$。对于边$(u,v)$，有转移方程$cnt2[v]+=cnt2[u]$。

然后对于最短路图上的每一个边$(u,v)$，$cnt1[u]*cnt2[v]$即为这个边被最短路经过的次数

定向最短路图

对于源点s和另一点t，和一条边$(u,v,w)$，如果满足$dis_s[u]+w+dis_t[v]=dis_s[t]$ 那么这条边就在从s到t的最短路上。其中 $dis_x[]$ 表示以x为源点的最短路

同余最短路

[国家集训队] 墨墨的等式

墨墨突然对等式很感兴趣，他正在研究 $\sum_{i=1}^n a_ix_i=b$ 存在非负整数解的条件，他要求你编写一个程序，给定 $n, a_{1\dots n}, l, r$，求出有多少 $b\in[l,r]$ 可以使等式存在非负整数解。

首先一个特判，如果 $a_i$ 为 0，那么他应该被忽略掉

然后我们选择 $a_i$ 中最小的那个数作为 base。

然后再一个特判，base=1时，l 到 r 都可以作为一个解，直接输出 (r-l+1)

先考虑 $[1,r]$ 中能满足等式的数，最后差分即可得出 $[l,r]$ 的答案。

接下来就是同余最短路了。

考虑将 $[1,r]$ 中所有的数字按%base的余数分成base个类。然后对于每一同余类，我们用同余最短路求出若干个 $a_i$ 之间相互来回加能加出的最小的，%base等于一个值的数。

求出最小的这个数有什么用？比如base=3，余数为1中最小能加出来的数为10，那么显然13也可以被拼出来，16也可以，19也可以...，我们可以通过不断调整base即可。

那如果不仅调整base，还调整其他的 $a_i$ 呢？那样会使得余数不再为1了，就是另外一个同余类了。

我们可以按照下面的方式建图

cpp
1
2
3
for(int i=0;i<base;i++)
	for(int j=1;j<=n;j++) 
		if(a[j]!=base) add(i,(i+a[j])%base,a[j]);

dijkstra时和普通的没啥区别

然后对于一个同余类，余数为 $i$，$(r-dis[i])/base+1$ 即为能拼出来的数的个数，枚举 $i$ 把答案全部相加即可

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<bits/stdc++.h>
#define int long long
using namespace std;

int base=0x3f3f3f3f,dis[500005],vis[500005],head[500005],a[20],n,l,r,size;
struct Edge{int next,to,w;} edge[10000007];
inline void add(int u,int v,int w){edge[++size].to=v,edge[size].w=w,edge[size].next=head[u],head[u]=size;}

typedef pair<int,int> pii;
inline void dijkstra(){
	memset(dis,0x3f,sizeof dis);
	dis[0]=0;
	priority_queue<pii,vector<pii>,greater<pii> > q;
	q.push(make_pair(0,0));
	while(!q.empty()){
		int now=q.top().second;q.pop();
		if(vis[now]) continue;
		vis[now]=true;
		for(int i=head[now];i;i=edge[i].next){
			int w=edge[i].w;
			int to=edge[i].to;
			if(dis[to]>dis[now]+w){
				dis[to]=dis[now]+w;
				if(!vis[to]) q.push(make_pair(dis[to],to));
			}
		}
	}
}

signed main(){
	cin>>n>>l>>r;
	int nn=0;
	for(int x,i=1;i<=n;i++){
		cin>>x;
		if(!x) continue;
		a[++nn]=x,base=min(base,a[nn]);
	}
	n=nn;
	if(base==1) return cout<<(r-l+1),0;
	for(int i=0;i<base;i++)
		for(int j=1;j<=n;j++) 
			if(a[j]!=base) add(i,(i+a[j])%base,a[j]);
	dijkstra();
	int ansr=0,ansl=0;
	for(int i=0;i<base;i++){
		if(r<dis[i]) continue;
		ansr+=(r-dis[i])/base+1;
	}
	l--;
	for(int i=0;i<base;i++){
		if(l<dis[i]) continue;
		ansl+=(l-dis[i])/base+1;
	}
	//for(int i=0;i<base;i++) cout<<dis[i]<<' ';
	cout<<ansr-ansl;
	return 0;
}

有向图最小环

首先枚举起点 $s=1...n$。使用dijkstra算法，则s一定是第一个出堆的节点。对s的连边进行松弛操作，松弛后令 $dis[s]$ 为正无穷，然后继续进行。当s第二次从堆中取出时，$dis[s]$ 即为最小环长度

spfa算法

只要使用spfa算法，无论是最短路还是负环，都有被卡的风险。最短路如果没有负边权一定要选择dijkstra算法。判断负环建议使用拓扑排序

最短路

spfa适用于存在负边权的图求单源最短路

和dijkstra不同，$vis[]$ 表示点是否在队列中。当一个点的距离被松弛时，把这个点加入队列中

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int dis[100005];
int vis[100005];
void spfa(int x){
	memset(dis,0x3f,sizeof(dis));
	queue<int> q;
	dis[x]=0;
	q.push(x);
	while(!q.empty()){
		int now=q.front();q.pop();
		vis[now]=false;
		for(int i=head[now];i;i=edge[i].next){
			int to=edge[i].to;
			int w=edge[i].w;
			if(dis[to]>dis[now]+w){
				dis[to]=dis[now]+w;
				if(!vis[to]){
					vis[to]=true;
					q.push(to);
				}
			}
		}
	}
}

判断负环

只需要记录每个点入队次数（起点不算）。在松弛后，如果入队了，就$cnt[to]++$，然后立刻判断if(cnt[to]>=n)

cpp
1
2
3
4
5
6
7
8
9
10
...
				if(!vis[to]){
					cnt[to]++;
					if(cnt[to]>=n){
						return true;//存在负环 
					}
					vis[to]=true;
					q.push(to);
				}
...

差分约束

限制上限

标准式：$x_i-x_j\le c$，等价于从$j$向$i$连接一条边权为$c$的有向边
按照上面建图，然后再添加一个超级源点

cpp
1
2
3
for(int i=1;i<=n;i++){
	add(n+1,i,0);
}

这里的0就是限制的上限！最后求出的结果不会大于0，小于等于0
使用spfa跑最短路（以超级源点为起点），顺便判断负环

注意：判断负环的时候要和n+1比较，因为引入了超级源点

cpp
1
if(cnt[to]>=n+1) return true;

存在负环说明无解，有解的话，$dis[]$就是一组解

限制上限后，所有的解都会尽量向上限靠近，所以也可以视为求的是最大解

最大解，限制上限，小于号，跑最短路

限制下限

标准式：$x_i-x_j\\ge c$，等价于从$j$向$i$连接一条边权为$c$的有向边

剩下的同上。如果是add(n+1,i,1);，则说明最后求出的结果不会小于1，大于等于1

限制下限后，所有的解都会尽量向下限靠近，所以也可以视为求得是最小解

最小解，限制下限，大于号，跑最长路

tarjan算法

染色

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
//tarjan部分 
int _time=0;//time是关键字，要加下划线 
int dfn[10004],low[10004];
stack<int> s;
int lock[10004];
//染色部分
int tot=0;
int id[10004];
void dfs(int x);
void tarjan(){
	for(int i=1;i<=n;i++){
		if(!dfn[i]) dfs(i);
	}
}
void dfs(int x){
	dfn[x]=low[x]=++_time;
	s.push(x);
	lock[x]=true;
	for(int i=head[x];i;i=edge[i].next){
		int to=edge[i].to;
		if(!dfn[to]){
			dfs(to);
			low[x]=min(low[x],low[to]);
		}else if(lock[to]) low[x]=min(low[x],dfn[to]);
	}
	if(low[x]==dfn[x]){
		tot++;
		while(true){
			int k=s.top();s.pop();
			lock[k]=false;
			id[k]=tot;
			if(k==x) break;
		}
	}
}

缩点

和染色类似。不同的是，缩点时，强连通分量的id不需要自己分配，可以直接选择一个点的编号来代表。这为之后重建图提供便利

cpp
1
2
3
4
5
6
7
8
9
10
11
...
	if(dfn[x]==low[x]){
		while(true){
			int k=s.top();s.pop();
			lock[k]=false;
			id[k]=x;//////
			if(k==x) break;
			w[x]+=w[k];//必要时，可以将点权也塞进缩到的点里面
		}
	}
...

重建图

重建图后就变成DAG了，往往需要用拓扑dp，参考dp部分

cpp
1
2
3
4
5
6
7
8
void rebuild(){
	for(int i=1;i<=m;i++){
		int x=id[edge[i].from],y=id[edge[i].to];
		if(x!=y){
			nadd(x,y);
		}
	}
}

桥与边双连通分量

求解

桥是在无向图中定义的

桥：将一个边删掉，整个图变得不连通了。这样的边称为桥

因为只需要考虑low和dfn的关系，所以不需要$lock[]$和$stack$

求桥时可能会有重边，重边会影响到桥。解决办法就是第一次遍历到fa时continue掉，后面再遍历到的话，就当做普通的点一样，不continue

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void dfs(int x,int fa){
	dfn[x]=low[x]=++_time;
	bool flag=false;
	for(int i=head[x];i;i=edge[i].next){
		int to=edge[i].to;
		if(to==fa&&!flag){
			flag=true;
			continue;
		}
		if(!dfn[to]){
			dfs(to,x);
			if(low[to]>dfn[x]){//如果目标不能回溯到当前节点，那么当前节点的目标节点之间必有桥 
				tot++;
				ans[tot].from=min(x,to);
				ans[tot].to=max(x,to);
			}
			low[x]=min(low[x],low[to]);
		}else low[x]=min(low[x],dfn[to]);
	}
}

边双连通分量：将所有的桥都去掉，剩下的连通块就是边双连通分量

注意由于是无向图，标记一个桥后实际上是要去掉两条边。不用真的去掉，打个标记，dfs的时候判断一下即可

性质

• 边双连通分量中的任意两点之间都有至少两条不重复路径

• 将边双缩成一个点，和桥一起就会构成一个树，设树中度数为1的节点有k个。则，一个有桥的连通图，通过加边变为边双，k=1至少要添加的边数为0，其他情况下至少添加边数为 $(k+1)/2$ （即尽可能叶子节点之间两两配对，2个至少一条边，3个至少两个，4个至少两个个...）

割点与点双连通分量

求解

割点是在无向图中定义的

割点：去掉一个点以及这个点所连的边之后，图不连通了，这个点称为割点

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int _time=0;
int dfn[20004],low[20004];
bool cut[20004];//是否为割点 
void tarjan(int x,int fa){
	dfn[x]=low[x]=++_time;
	int child=0;//记录子树数目 
	for(int i=head[x];i;i=edges[i].next){
		int to=edges[i].to;
		if(to==fa) continue;
		if(!dfn[to]){
			child++;
			tarjan(to,x);
			low[x]=min(low[x],low[to]);
			if(low[to]>=dfn[x]){//最多只能回溯到当前点，更早的点回溯不了 
				cut[x]=true;
			}
		}
		else low[x]=min(low[x],dfn[to]);
	}
	if(x==fa&&child>=2) cut[x]=true;//如果当前节点为根节点且根节点有两个子树，根节点为割点 
}

和求桥类似，low[to]>=dfn[x] 时 x 即为割点。注意还是要特判一种情况：为根节点且有两个或两个以上子树的点也为割点

点双连通分量：不存在割点的极大连通子图

值得注意的是，单独的一个点也是点双连通分量

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int n,m;
int _time=0;
int dfn[500005],low[500005];
int vis[500005];
stack<int> s;
int tot=0;
vector<int> ans[500005];
void dfs(int x,int fa){
	int son=0;
	dfn[x]=low[x]=++_time;
	s.push(x);
	for(int i=head[x];i;i=edge[i].next){
		int to=edge[i].to;
		if(to==fa) continue;
		if(!dfn[to]){ 
			son++;
			dfs(to,x);
			low[x]=min(low[x],low[to]);
			if(low[to]>=dfn[x]){
				tot++;
				int las=0;
				while(true){
					int k=s.top();s.pop();
					ans[tot].push_back(k);
					if(k==to) break;//弹到to 
				}
				ans[tot].push_back(x);//再附赠个割点 
			}
		}else low[x]=min(low[x],dfn[to]);
	}
	if(fa==0&&son==0) ans[++tot].push_back(x);//特判孤立点 
	//不需要像求割点一样判断son>=2
}

注意这回特判的是孤立点

圆方树

• 原图中的点被称为圆点。

• 求得原图中所有点双连通分量，对每一个点双都新建一个节点，这类点被称为方点。

• 删去原图中所有边，令每一个圆点向包含该点的点双对应的方点连边。

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int n,m,tot,head[_],size,heada[_],sizea;
struct Edge{int next,to;} edge[_],edgea[_];
inline void add(int u,int v){edge[++size].next=head[u],head[u]=size,edge[size].to=v;}
inline void adda(int u,int v){edgea[++sizea].next=heada[u],heada[u]=sizea,edgea[sizea].to=v;}

int dfn[_],low[_],timer=0;
stack<int> s;
void dfs(int x,int fa){
	dfn[x]=low[x]=++timer;
	s.push(x);
	for(int i=head[x];i;i=edge[i].next){
		int to=edge[i].to;
		if(!dfn[to]){
			dfs(to,x);
			low[x]=min(low[x],low[to]);
			if(low[to]>=dfn[x]){
				tot++;//扫到一个割点就开一个方点
				adda(x,tot);adda(tot,x);
				while(true){
					int now=s.top();s.pop();
					adda(tot,now);adda(now,tot);
					if(now==to) break;
				}
			}
		}else if(to!=fa) low[x]=min(low[x],dfn[to]);
	}
}

tot=n;
dfs(1,0);

注意圆方树空间开2倍，而且不需要特判孤立点了

性质

• 除了只有两个点的点双，其他点双都满足：任意两点间都存在至少两条点不重复路径

• 任意一个割点都至少存在两个点双中

• 不是割点的点只存在于一个点双中

欧拉路

概念性质

1. 欧拉回路：图中经过每条边，且只经过一次的回路

2. 欧拉路径：图中经过每条边，且只经过一次的路径

3. 欧拉图：存在欧拉回路的图

4. 半欧拉图：只存在欧拉路径，但不存在欧拉回路的图

有以下性质：

对于无向图

1. 无向图为欧拉图，当且仅当这个图为连通图，且所有顶点的度为偶数

2. 无向图为半欧拉图，当且仅当这个图为连通图，且除了有两个顶点的度为奇数外，其他点的度都为偶数

对于有向图

1. 有向图为欧拉图，当且仅当这个图的基图连通，且所有顶点的入度等于出度

2. 有向图为半欧拉图，当且仅当这个图的基图连通，且一个点的出度比入度大1，一个点的入度比出度大1，其他点的出度等于入度

求欧拉路径

有向图

首先是一堆判定存在的代码

cpp
1
2
3
4
5
6
7
8
    int s=1;
	int cnt1=0,cnt2=0;
	for(int i=1;i<=n;i++){
		if(in[i]!=out[i]) flag=false;
		if(out[i]-in[i]==1) cnt1++,s=i;
		if(in[i]-out[i]==1) cnt2++; 
	}
	if((!flag)&&!(cnt1==cnt2&&cnt1==1)) return !(cout<<"No");

然后从起点，直接dfs走起

$del[]$ 存一个点的遍历起点，这个再遍历回这个点之后就可以快速跳过已经遍历过的边

cpp
1
2
3
4
5
6
7
void dfs(int x){
	for(int i=del[x];i<g[x].size();i=del[x]){
		del[x]++;
		dfs(g[x][i]);
	}
	ans.push(x);
}

注意保存答案的时候一定要使用回溯+栈来保存，不能在for循环内直接保存答案

无向图

无向图如果类比有向图使用del数组+记录fa的话会出现各种奇怪错误。因此建议使用比较保守的邻接矩阵+ $O(mn)$ 算法

还要注意使用栈，先dfs再记录答案

cpp
1
2
3
4
5
6
7
8
9
stack<int> s;
void dfs(int x){
	for(auto to:ve[x]){
		if(ma[to][x]==maxx[to][x]) continue;//这里是用于处理重边，记录重边遍历了多少次，如果重边都走完了就不走了
		ma[to][x]++,ma[x][to]++;
		dfs(to);
	}
	s.push(x);
}

匈牙利算法

cpp
1
2
3
4
5
6
7
8
vector<int> ve[101];
int match[101],t[101];
bool dfs(int x,int tag){
	if(t[x]==tag) return false;
	t[x]=tag;
	for(int to:ve[x]) if(!match[to]||dfs(match[to],tag)) return match[to]=x,true;
	return false;
}