图论

强连通分量

• $dfn[x]$ 为结点 $x$ 搜索的时间次序。
• $low[x]$ 为 $u$ 或 $u$ 的子树（经过最多一条后向边或栈中横叉边）能够回溯到的最早的栈中结点的编号。
• 由定义可以得出：

$low[x]=\min$
{ \{ {
$dfn[x]$
$low[y],(x,y)为树枝边，x为y的父结点$
$dfn[y],(x,y)为后向边或指向栈中结点的横叉边$
$\}$

inline void Tarjan(int x)
{
	dfn[x] = low[x] = ++tis;
	stk[++top] = x;
	ins[x] = true; 
	int y;
	for (arc *e = adj[x]; e; e = e->nxt)
		if (!dfn[y = e->to])
		{
			Tarjan(y);
			CkMin(low[x], low[y]);
		}
		else if (ins[y])
			CkMin(low[x], dfn[y]);
	if (dfn[x] == low[x])
	{
		++C;
		do
		{
			y = stk[top--];
			ins[y] = false;
			col[y] = C;
		}while (y != x);
	}
}
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

桥

• 无向图中 $low[x]$ 为 $x$ 或 $x$ 的子树经过最多一条后向边能够追溯到的树中结点的次序号。
• 根据定义，有：

$low[x]=\min$
{ \{ {
$dfn[x]$
$dfn[y],(x,y)为后向边$
$low[y],(x,y)为树枝边$
$\}$

• 桥 $(x,y)$ 的判断条件： $(x,y)$ 为树枝边且 $dfn[x]<low[y]$。
• 将桥标记后用并查集确定边双连通分量。

对于一个有桥的连通图，求加最少数量的边，使其变为边双连通图。
用 $\text{Tarjan}$ 求出边双，将边双缩为一点，则原图变为一颗树。
记这棵无根树中度为 $1$ 的点数为 $leaf$，则所加最少边数为 $\lfloor \frac{leaf+1}{2}\rfloor$。

inline void Tarjan(int x)
{
	dfn[x] = low[x] = ++tis;
	int y;
	for (int e = adj[x]; e; e = nxt[e])
	{
		if (e == (up[x] ^ 1)) //树枝边的反相边要注意判断
			continue;
		if (!dfn[y = to[e]])
		{
			up[y] = e;
			Tarjan(y);
			CkMin(low[x], low[y]);
			if (dfn[x] < low[y])
				bridge[e] = bridge[e ^ 1] = true;
		}
		else 
			CkMin(low[x], dfn[y]);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

割点

• $low[x]$ 定义同上。
• $x$ 为割点的判断条件：

1. $x$ 为树根，且 $x$ 有多于一个的子树。
2. $x$ 不为树根，$(x,y)$ 为树枝边且 $dfn[x]\le low[y]$。

• 在求割点的过程中就能顺便求出点双连通分量。
• 在搜索图时，每找到一条树枝边或后向边（注意实现时后向边的反向边不应加入栈中），就把这条边加入栈中。若某点 $x$ 满足 $(x,y)$ 为树枝边且 $dfn[x]\le low[y]$ ，把边从栈顶一个个取出，直到遇到了边 $(x,y)$，取出的这些边与其相连的点，组成一个点双连通分量。
• 与求割点不同，求点双时并不需要判断树根，方便将所有点双取出。

典例 POJ2942

• 以下的奇环和偶环均指简单环。
• 建出原图的补图，则一名骑士能够参加会议当且仅当他在图中的一个奇环上。
• 易知奇环一定只在某个点双内部。
• 结论 若某个点双内存在奇环，则对于该点双内所有点，都存在某个奇环，使得该点在该奇环上。

证明 若某点在偶环上，则一定存在一个偶环与已知的奇环有公共边，则可将偶环和已知的奇环合并得到一个新的奇环。

Shopee_Code_League_2020:Shopee登月比赛2的资料好

zip 0星 超过10%的资源 5.66MB

下载

• 用二分图染色判断每个点双中是否存在奇环即可。
• 完整代码：

#include 
#include 

template <class T>
inline void read(T &res)
{
	char ch;
	while (ch = getchar(), !isdigit(ch));
	res = ch ^ 48;
	while (ch = getchar(), isdigit(ch))
		res = res * 10 + ch - 48;
}

template <class T>
inline void CkMin(T &x, T y) {x > y ? x = y : 0;}

const int N = 1e3 + 5;
const int M = 2e6 + 5;

int fa[N], col[N], dfn[N], low[N], stkx[M], stky[M];
int tis, n, m, top;
bool edge[N][N], inc[N], ans[N];

struct arc
{	
	int to;
	arc *nxt;
}p[M], *adj[N], *T = p;

inline void linkArc(int x, int y)
{
	(++T)->nxt = adj[x]; adj[x] = T; T->to = y;
	(++T)->nxt = adj[y]; adj[y] = T; T->to = x;
}

inline bool dfsColoring(int x)
{
	for (arc *e = adj[x]; e; e = e->nxt)
	{
		int y = e->to;
		if (col[y] == -1)
		{
			col[y] = col[x] ^ 1;
			if (!dfsColoring(y))
				return false;
		}
		else if (col[y] == col[x])
			return false;
	}
	return true;
}

inline void solvePBC(int x, int y)
{
	T = p;
	for (int i = 1; i <= n; ++i)
		adj[i] = NULL;
	int u, v;
	do
	{
		u = stkx[top], v = stky[top];
		linkArc(u, v);
		inc[u] = inc[v] = true;
		--top;
	}while (x != u || y != v);

	for (int i = 1; i <= n; ++i)
		col[i] = -1;
	col[x] = 0;
	
	if (!dfsColoring(x))
	{
		for (int i = 1; i <= n; ++i)
			if (inc[i])
				ans[i] = true;
	}
	
	for (int i = 1; i <= n; ++i)
		inc[i] = false;
}

inline void Tarjan(int x)
{
	dfn[x] = low[x] = ++tis;
	for (int y = 1; y <= n; ++y)
	{
		if (y == fa[x] || !edge[x][y])
			continue;
		if (dfn[y] < dfn[x]) // 包含条件 !dfn[y]
		{
			++top;
			stkx[top] = x;
			stky[top] = y;
		}
		if (!dfn[y])
		{
			fa[y] = x;		
			Tarjan(y);
			CkMin(low[x], low[y]);
			if (dfn[x] <= low[y])
				solvePBC(x, y);
		}
		else
			CkMin(low[x], dfn[y]);
	}
}

int main()
{
	while (1)
	{
		read(n); read(m);
		if (!n && !m)
			break ;
		for (int i = 1; i <= n; ++i)
			ans[i] = false;
		for (int i = 1; i <= n; ++i)
			for (int j = 1; j <= n; ++j)
				edge[i][j] = i == j ? false : true;
		for (int i = 1, x, y; i <= m; ++i)
		{
			read(x); read(y);
			edge[x][y] = edge[y][x] = false;
		}
		tis = top = 0;
		for (int i = 1; i <= n; ++i)
			dfn[i] = low[i] = fa[i] = 0;
		for (int i = 1; i <= n; ++i)
			if (!dfn[i])
				Tarjan(i);
		int fans = 0;
		for (int i = 1; i <= n; ++i)
			fans += !ans[i];
		printf("%d\n", fans);
	}	
	return 0;
}
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137

圆方树

• 对每个点双连通分量建一个新点，每个点向其所属的点双连边，形成树结构。
• 具体应用待补充。

2-SAT

• $\text{2-SAT}$ 问题指的是解下列形式的布尔方程：
  $$(a\vee b)\wedge (c\vee d)\wedge (e\vee f)\wedge \dots$$
• 其中 $a,b,c,\dots$ 称为文字，是一个布尔变量或其否定。
• 利用 $\Rightarrow$（蕴含） 将每个子句 $(a\vee b)$ 写成等价形式 $(\neg a\Rightarrow b\wedge \neg b\Rightarrow a)$，对每个布尔变量 $x$ 构造两个顶点 $x$ 和 $\neg x$，以 $\Rightarrow$ 关系为边建立有向图。
• 若存在 $x$ 和 $\neg x$ 在同一强连通分量内，则无解。
• 对强连通分量缩点后的图求拓扑序，则若 $x$ 所在的强连通分量的拓扑序在 $\neg x$ 所在的强连通分量的拓扑序之后，则 $x$ 为真，否则 $\neg x$ 为真。
• 强连通分量的编号即为逆拓扑序。
• 常见的等价形式转换：
  • $(x=1)\iff (\neg x\Rightarrow x),(x=0)\iff (x\Rightarrow \neg x)$
  • $\neg (a\vee b)\iff (a\Rightarrow \neg b\wedge b\Rightarrow \neg a)$
  • $k$ 个点中至多选一个，令这 $k$ 个点分别为 $a_1,a_2,\dots a_k$，新建 $2k$ 个点，$pr{e}_i$ 表示 $[1,i]$ 均不选，$su{f}_i$ 表示 $[i,k]$ 均不选，作如下连边：
    • $a_i\Rightarrow pr{e}_{i-1},a_i\Rightarrow su{f}_{i+1}$
    • $pr{e}_i\Rightarrow pr{e}_{i-1},pr{e}_i\Rightarrow \neg a_i$
    • $su{f}_i\Rightarrow su{f}_{i+1},su{f}_i\Rightarrow \neg a_i$
• 上述算法只适用于判断可行性并给出一种可行方案。

欧拉回路

• 设图 $G=(V,E)$。
• 欧拉回路/路径 图 $G$ 中经过每条边一次并且仅一次的回路/路径。
• 欧拉图 存在欧拉回路的图。
• 半欧拉图 存在欧拉路径但不存在欧拉回路的图。
• 基图 忽略有向图所有边的方向，得到的无向图。
• 定理1 无向图 $G$ 为欧拉图，当且仅当 $G$ 为连通图且所有顶点的度为偶数。
• 定理2 无向图 $G$ 为半欧拉图，当且仅当 $G$ 为连通图且除了两个顶点的度为奇数之外，
  其它所有顶点的度为偶数。
• 定理3 有向图 $G$ 为欧拉图，当且仅当 $G$ 的基图连通，且所有顶点的入度等于出度。
• 定理4 有向图 $G$ 为半欧拉图，当且仅当 $G$ 的基图连通，且存在顶点 $x$ 的入度比出度
  大 1、$y$ 的入度比出度小 1，其它所有顶点的入度等于出度。
• 求欧拉图 $G$ 的欧拉回路：

inline void findCircuit(int x)
{
	for (int &e = adj[x]; e; e = nxt[e])
		if (!vis[e])
		{
			int c = e;
			vis[c] = true; 
			if (type & 1) // type = 1 为无向图，type = 0 为有向图
				vis[c ^ 1] = true;
			findCircuit(to[c]);
			stk[++top] = c;
		}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

• 若题目要求用简单环覆盖图中所有边，则先求出欧拉回路，将欧拉回路上的边依次入栈，一旦入栈过程中发现有重点，则不断弹栈至重点处，则弹栈取出的所有边组成一个简单环，最终即可得到一个简单环的覆盖方案。

Prüfer 序列

• 对树建立 Prüfer 序列
  • 每次选择一个编号最小的叶子结点删除，在序列中记录它连接的那个结点。
  • 重复 $n-2$ 次直至剩下两个结点，算法结束。
  • 线性实现上述过程只需用指针 $p$ 记录当前编号最小的叶子结点，若删点后产生的新的叶子结点比 $p$ 小则继续删除这个叶子结点不产生新的叶子结点或产生的叶子结点比 $p$ 大。
• Prüfer 序列的性质
  • 构造完 Prüfer 序列原树剩下的两个结点之一一定是编号最大的结点 $n$。
  • 每个结点在序列中出现的次数是其度数减一，没有出现的就是叶子结点。
• 用 Prüfer 序列重建树
  • 由 Prüfer 序列的性质还原出每个点的度数。
  • 依次枚举 Prüfer 序列上的点，选择一个度数为 1 且编号最小的结点与之连接，同时将两者的度数减一。
  • 重复 $n-2$ 次后只剩下两个度数为 1 的点，将它们建立连接，算法结束。
  • 线性实现上述过程同样是用指针 $p$ 记录度数为 1 且编号最小的结点，具体做法类似。

inline void TreeToPrufer()
{
	for (int i = 1, x; i < n; ++i)
	{
		read(fa[i]);
		++deg[fa[i]];
	}
    // 这里的 fa[i] 指以 n 为根时结点 i 的父结点
	int p = 1, x = 0;
	for (int i = 1; i <= n - 2; ++i)
		if (x && x < p)
		{
			ans[i] = fa[x]; 
			x = !--deg[fa[x]] ? fa[x] : 0;
		}
		else
		{
			while (deg[p])
				++p;
			ans[i] = fa[p];
			x = !--deg[fa[p]] ? fa[p] : 0;
			++p;
		}
}

inline void PruferToTree()
{
	for (int i = 1; i <= n - 2; ++i)
	{
		read(ans[i]);
		++deg[ans[i]];
	}
	int p = 1, x = 0;
	for (int i = 1; i <= n - 2; ++i)
		if (x && x < p)
		{
			fa[x] = ans[i];
			x = !--deg[ans[i]] ? ans[i] : 0;
		}
		else
		{
			while (deg[p])
				++p;
			fa[p] = ans[i];
			x = !--deg[ans[i]] ? ans[i] : 0;
			++p;
		}
	for (int i = 1; i < n; ++i)
		if (!fa[i])
		{
			fa[i] = n;
			break ;
		}
}
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

• Cayley 公式 完全图 $K_n$ 有 $n^{n-2}$ 棵生成树。

证明 由构造和还原过程可知，任意一个长度为 $n-2$、值域为 $[1,n]$ 的整数序列都可以通过 Prüfer 序列双射对应一个生成树。

• 结论1 $n$ 个结点有标号有根树的数量为 $n^{n-1}$。
• 结论2 $n$ 个结点的度数依次为 $d_1,d_2,\dots ,d_n$ 的无根树的数量为 $\frac{(n-2)!}{\prod _{i=1}^n(d_i-1)!}$。
• 结论3 把 $n$ 个点划分为 $k$ 个连通块，已知第 $i$ 个连通块的内部连边情况和大小 $a_i$，包含所有连通块的生成树数量为 $n^{k-2}\prod _{i=1}^k{a}_i$。

证明 待补充。