图论

图论（英语：Graph theory）是组合数学的一个分支。图是图论的主要研究对象。图是由若干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物，连接两顶点的边则用于表示两个事物间具有这种关系。

图论起源于著名的柯尼斯堡七桥问题。该问题于1736年被欧拉解决，因此普遍认为欧拉是图论的创始人。

基本概念

图

图（Graph）用于表示物件与物件之间的关系，是图论的基本研究对象。一张图由一些小圆点（称为顶点或结点）和连结这些圆点的直线或曲线（称为边）组成。

二元组的定义

一张图 $G$ 是一个二元组 $(V, E)$ ，其中 $V$ 称为顶点集， $E$ 称为边集。它们亦可写成 $V(G)$ 和 $E(G)$ 。 $E$ 的元素是一个二元组数对，用 $(x, y)$ 表示，其中 $x, y \in V$ 。

有向图和无向图

如果给图的每条边规定一个方向，那么得到的图称为有向图，其边也称为有向边。在有向图中，与一个节点相关联的边有出边和入边之分，而与一个有向边关联的两个点也有始点和终点之分。相反，边没有方向的图称为无向图。

简单图

一个图如果

没有重边。即没有两条边，它们所关联的两个点都相同（在有向图中，没有两条边的起点终点都分别相同）；
没有自环。即每条边所关联的是两个不同的顶点。
则称为简单图（Simple graph）。

度

度（Degree）：一个顶点的度是指与该顶点相关联的总边数，顶点 $v$ 的度记作 $d(v)$ 。度和边有如下关系：
$\sum_{v \in V} d(v) = 2|E|$ 。

出度和入度

出度（Out-degree）和入度（In-degree）：对有向图而言，顶点的度还可分为出度和入度。一个顶点的出度为 $d_o$ ，是指有 $d_o$ 条边以该顶点为起点，或说与该点关联的出边共有 $d_o$ 条。入度的概念也类似。

子图

子图（Sub-Graph）：图 $H$ 称作图 $G$ 的子图如果 $V(H) \subseteq V(G)$ 以及 $E(H) \subseteq E(G)$ 。

如果图 $G$ 的子图 $H$ ，满足 $V(H) = V(G)$ ，即图 $H$ 包含图 $G$ 的所有顶点，则称 $H$ 是 $G$ 的生成子图。特别的如果子图 $H$ 是树，则称子图 $H$ 为生成树。

如果图 $G$ 的子图 $H$ ，满足对于 $u, v \in V(H)$ ，边 $(u, v)$ 在图 $H$ 中当且仅当边 $(u,v)$ 在图 $G$ 中，即图 $H$ 包含了图 $G$ 中所有两个端点都在 $V(H)$ 中的边，则称 $H$ 是 $G$ 的导出子图。

补图

一个图 $G$ 的补图（complement）是一个图有着跟 $G$ 相同的点，而且这些点之间有边相连当且仅当在 $G$ 里面他们没有边相连。

完全图

完全图是所有顶点两两相邻的图。 $n$ 阶完全图，记作 $K_n$ 。 $n$ 阶完全图有 $n(n-1)/2$ 条边。

独立集

独立集（independent set）是图论中的概念。一个独立集是一个图中一些两两不相邻的顶点的集合。换句话说它是一个由顶点组成的集合 $S$ ，使得 $S$ 中任两个顶点之间没有边。等价地，图中的每条边至多有一个端点属于 $S$ 。

二分图

二分图指顶点可以分成两个不相交的集 $U$ 和 $V$ ，使得在同一个集内的顶点不相邻（没有共同边）的图，即 $U$ 和 $V$ 皆为独立集。

完全二分图

完全二分图是一种特殊的二分图，可以把图中的顶点分成两个集合 $X, Y$ ，使得集合 $X$ 中的所有顶点都与集合 $Y$ 中的所有顶点相连。若 $|X| = m, |Y| = n$ 则图 $G$ 计作 $K_{m, n}$ 。

平面图

平面图是可以画在平面上并且使得不同的边可以互不交叠的图。而如果一个图无论怎样都无法画在平面上，并使得不同的边互不交叠，那么这样的图不是平面图，或者称为非平面图。完全图K5和完全二分图K3,3（汤玛森图）是最“小”的非平面图。

NP完全

图论中有很多经典的NP完全问题

子图同构。输入图 $G$ 和图 $H$ 问是否存在 $G$ 的子图与 $H$ 同构。
哈密顿路径问题。输入无向图 $G$ 问是否存在经过每个点恰好一次的路径。
旅行推销员问题。输入无向图 $G$ 有边权，希望经过每个点恰好一次，并且权值和最小。
最大团。输入无向图 $G$ 求最大团。
最大独立集。输入无向图 $G$ 求最大独立集。
图着色问题。输入无向图 $G$ ，每个点染一个颜色，希望相邻的点颜色不同，问最小色数。

如果在做题中遇到类似问题，说明

转化中忽略了条件，比如最大独立集，一般图做不了，但是二分图可以做。
忽略了数据范围，旅行推销员问题是经典的状态压缩DP。
考查近似算法。很多NP完全问题，有效果不错的近似算法。

图的存储

参考单独页面图的存储

图的遍历

在竞赛中，经常需要计算出有多少个连通块和每个连通块的大小。
主要有以下三个方法

并查集
深度优先搜索(DFS)
广度优先搜索(BFS)

拉姆齐定理

要找这样一个最小的数 $R(k, l) = n$ ，使得 $n$ 个人中必定有 $k$ 个人相识或 $l$ 个人互不相识。

一个鸽笼原理的简单应用是证明 $R(3, 3) = 6$ 。

欧拉回路

见欧拉回路

参考题目

参考资料

图 (数学)

拉姆齐定理

图论 Graph Theory

存边

直接存
邻接链表 / vector
邻接矩阵 Prim / Floyd

有向边
无向边

直接存
(起点, 终点, 边权)
方便按边权排序，Kruskal

按起点排序（这一步可以计数排序）
记录每个点的第一条边和最后一条边是谁
通过循环可以得到起点相同的所有边

比如初始有
1 2
2 3
3 1
三条边

1 2
2 1
2 3
3 2
3 1
1 3

排序得到
1 2 // 0
1 3 // 1
2 1 // 2
2 3 // 3
3 1 // 4
3 2 // 5

first[1] = 0 从1出发的第一条边，下标是0
first[2] = 2
first[3] = 4
first[4] = 6

如果想访问从x出发的所有边
for (int i = first[x]; i < first[x + 1]; i++)
{

}
就可以了

邻接链表 adjacent list

使用vector

adjacent list or vector(ArrayList)

int head[];
struct Edge
{
int next; // use int to represent the index rather than pointer.
int to;
int weight;/
}

enumerate all edges from x

for (int i = head[x]; i != 0; i = a[i].next)
{
	if (a[i].to   a[i].weight)
	{

    }

}

vector<pair<int, int> > a[1000020];

from x to y length z
a[x].push_back(make_pair(y, z));

需求
给定起点x，找到起点x出发的所有的边
主要矛盾：一个点的出边，可能很多（n个）可能很少（1个）
邻接链表

优点比较快
缺点比较麻烦
只能访问全部，不方便删除或者排序

邻接链表，后加入的会先被访问到

每个点x维护 head[x] 指向这个链表的第一个边

每个边除了维护自身的信息比如 to[i] length[i] 再维护一个 next[i] 表示链表
有的人会用结构体把这3个变量存在一起，这个不涉及到结构体做参数和返回值，所以用不用都可以
有的人会用指针实现链表存边
对于做比赛来说，没必要用指针，凡是需要用 pointer 的地方，都可以记录数组下标
建议不要用指针，因为很难调试
对于做比赛来说，一般不用 new 和 delete

如果存双向边，需要开双倍数组

for (int i = head[x]; i; i = next[i]) // 如果 i==0 认为没有边了，有的人会用 -1 表示没有边
{
有一条边从 x 到 to[i] 边长是 length[i]
如果i是奇数
那么i的反向边是i+1
如果i是偶数
那么i的反向边是i-1
如果不知道x，如何确定第i条边是从哪里出发的
看反向边to是多少
}

如果 head[x] 是 0，那么说明没有从 x 出发的边

head[x] 是第一条边
next[head[x]] (如果有) 是第二条边
next[next[head[x]]] (如果有) 是第三条边

void addEdge(int x, int y, int z) // x 到 y 边长是 z
{
edgecnt++;
next[edgecnt] = head[x]
head[x] = edgecnt;
length[edgecnt] = z;
}

有的人会利用
如果我们加双向边
那么 1 和 2 互为反向边，3 和 4 互为反向边
用链表可以很容易的找到反向边
这个在网络流中有用
一般为了方便
都会从2开始存
让 2和3一组 4和5一组
这样的话i的反向边是 i^1

vector<pair<int, int> > a[100020];
(终点, 权值)
优点好写，可以完成排序等操作
缺点：慢

一般只要输入的是
(起点, 终点, 边长)
都是这样存，可以避免重边

vector会预留16个位置，
用完之后，倍增，大小乘以2
这样平均下来是O(1)

邻接矩阵 adjacent matrix

it depends on the input.
(x, y, z1)
(x, y, z2)

from x to y length z
a[y][x] = z

点数n
a[i][j]表示i到j的边的情况
需要n*n空间
如果点数很大，一般是开不了的。

如果输入不是n*n的数组，非常不建议用这个方法
因为有很多问题
比如输入有重边怎么办？

只用Floyd用邻接矩阵

最短路

特殊的最短路：

边权为1的最短路，可以用BFS解决
有向无环图的最短路，可以用拓扑排序解决

4个算法

Bellman-Ford 基本没用
Dijkstra 堆优化的版本非常常见，几乎所有最短路都是
Floyd 任意两点之间的最短路，可以用来求最小环传递闭包
SPFA 中国人发明的算法，外国人基本不知道。队列优化版的BF，可以求负环。
如何求最短路的方案？
最短路树，最短路图

有向图求
所有点到某一点的最短路
等价于
某一点到所有点的最短路
只需要翻转图中所有边

差分约束

Bellman-Ford
一个起点，到所有点的最短路

d[i] 从起点到 i 的最短路的长度

初始化
d[起点] = 0
d[非起点] = 正无穷大

松弛操作

从 x 到 y 长度是 z 的边
if (d[y] > d[x] + z)
{
d[y] = d[x] + z;
}

for (int i = 0; i < 点数-1; i++) // 最坏情况，需要n-1轮
{
for (枚举所有的边(任意顺序) (x, y, z))
{
对(x, y, z)做松弛操作
}
}

最终求出最短路后，对于任意边(x, y, z)一定满足
d[y] <= d[x] + z

可以用队列优化获得 SPFA
可以用优先队列优化获得 Dijkstra

Dijkstra
要求所有边都是非负的
可以 Prim 对比
需要用到 priority_queue 或者 set 保证每次取到距离最小的点
需要注意 priority_queue 默认大的在前
priority_queue 不支持删除任意点，需要特殊处理
每一个点恰好出队1次
每一条边恰好被枚举到1次
时间复杂度 (n + m) log n

Dijkstra 可以堆优化， Prim 也可以堆优化
Prim 堆优化不如 Kruskal
暴力的Prim 在完全图上时间复杂度是 O(n^2) 比堆优化的要快
Dijkstra 在完全图上暴力比堆优化快

假设图中所有边权都是1，不需要使用优先队列，使用队列就足够了。

while (q.size() > 0) {
pair<int, int> u = q.top();
q.pop(); // 暴力 O(n) 堆优化 O(log n)
if (-u.first > d[u.second]) {
continue;
}
for (int i = 0; i < a[u.second].size(); i++) {
pair<int, int> e = a[u.second][i];
if (d[e.first] > d[u.second] + e.second) {
d[e.first] = d[u.second] + e.second;
q.push(make_pair(-d[e.first], e.first));
// 暴力 O(1) 堆优化 O(log n)
}
}
}

这种 Dijkstra 不是原版的 Dijkstra，是有区别的
为了在算法比赛中比较容易实现做出了一些改进
区别是省略一个标记数组

如果有负边权会怎样？
如果限制每个点只进队1次，会出错
如果不限制每个点只进队1次，会超时，时间复杂度变成指数

P1608 路径统计
两个点之间有多条长度相同的边，计算最短路方案数时只算1次
所以不能加入起点终点长度均一样的边，会导致出错。

方案数可能非常大，但是题目没有考虑这种情况。

P2384 最短路
取对数避免越界
可能会有精度问题

2939 [USACO09FEB]Revamping Trails G
分层图

Floyd
无向边看做两条有向边

初始的距离d[x][y] x到y的距离
我们定义一个数组 f[k][x][y] ，
表示只允许经过（不算起点和终点）结点1到k ，结点x到结点y的最短路长度。

f[0][x][y] = d[x][y] （不能有中间节点
f[n][x][y] 就是我们需要的答案

f[k][x][y] = min(f[k-1][x][k] + f[k-1][k][y], f[k-1][x][y])

for (k = 1; k <= n; k++) { // 枚举中间点
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]);
}
}
}

时间复杂度 O(n^3)

P2910 [USACO08OPEN]Clear And Present Danger S
直接做就可以了

无向图最小环
for (k = 1; k <= n; k++) {
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++) {
f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
}
}
for (int x = 1; x <= n; x++)
{
for (int y = 1; y <= n; y++)
{
最小环 = min(最小环, a[k][x] + a[k][y] + d[x][y]);
// 记录一下原图是什么
}
}
}
hdu 1599
传递闭包，bitset优化
对一个图DFS/BFS的时间复杂度O(n + m)
P4306 [JSOI2010]连通数
枚举起点
n * O(n + m)

f[i][j] == 1 表示 i 可以到 j
f[i][j] == 0 表示 i 不可以到 j

for (int k = 0; k < n; k++)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (f[i][k] && f[k][j])
{
f[i][j] = 1;
}
}
}
}

for (int k = 0; k < n; k++)
{
for (int i = 0; i < n; i++)
{
if (f[i][k])
{
for (int j = 0; j < n; j++)
{
if (f[k][j])
{
f[i][j] = 1;
}
}
}
}
}

for (int k = 0; k < n; k++)
{
for (int i = 0; i < n; i++)
{
if (f[i][k])
{
for (int j = 0; j < n; j++)
{
f[i][j] |= f[k][j];
}
}
}
}

bitset<2000> f[2000];
for (int k = 0; k < n; k++)
{
for (int i = 0; i < n; i++)
{
if (f[i][k])
{
f[i] |= f[k];
}
}
}

n^3

操作32位，
bool a[32], b[32];
unsigned a, b;
bitset<32> a, b;
for (int i = 0; i < 32; i++)
{
c[i] = a[i] | b[i];
}

c = a | b;
c = a | b;

bitset 3个用法

传递闭包
背包
高斯消元解异或方程

P2052 [NOI2011]道路修建
当时NOI现场，DFS是无法通过的，因为会爆栈，1000000层太多
需要long long

DFS一个树，经常需要的
没有根的，定一个根，选择1和n

void dfs(int x, int x的父亲节点)
{
for (枚举x的所有邻居i)
{
if (i != x的父亲节点)
{
dfs(i);
}
}
}

为了避免爆栈，使用BFS

P1514 引水入城

P1529 [USACO2.4]回家 Bessie Come Home

P1656 炸铁路

P1828 [USACO3.2]香甜的黄油 Sweet Butter

P3478 [POI2008]STA-Station
深度之和最大
求出每个点的深度之和
2次DFS的做法

第一次DFS，求出每个子树的答案（子树个根节点就是根节点，其他点到子树的根节点的距离）
根节点的答案，就是最终的答案了，其他节点的答案，没有考虑父亲节点方向的节点
第二次DFS，把根节点的答案传到所有节点

SP7363 TREESUM - Tree Sum
一个集合A
s0 = A集合中所有数字0次方的和
s1 = A集合中所有数字1次方的和
s2 = A集合中所有数字2次方的和

s0' = A集合中所有数字加一之后0次方的和
s1' = A集合中所有数字加一之后1次方的和
s2' = A集合中所有数字加一之后2次方的和

s0' = s0
s1' = s1 + s0
s2' = s2 + 2 s1 + s0
s3' = s3 + 3 s2 + 3 s1 + s0

P4827 [国家集训队] Crash 的文明世界
树形DP 两次DFS

如果一个题目，求每个点的xxx的答案，应该是2次DFS

深度之和最小
重心：删除重心之后，树变成了若干个更小的树，其中最大的最小。
删去重心之后，任意一个子树大小都<=n/2
特殊情况，一个树可以有2个重心。

P2845 [USACO15DEC]Switching on the Lights S

P3916 图的遍历
反向建图，先处理答案为n的，处理答案为n-1。。。。

P5318 【深基18.例3】查找文献
需要把每个点的出边排序

树 DFS序列
进出栈序
1 2 3 3 4 4 2 5 5 1
总长度2n，每个点恰好出现2次

同一个子树的点一定是连续的一段

输入2个点x和y判断x和y的关系

x == y
x是y的祖先
y是x的祖先
x和y没关系

区间的包含关系等价于图中的祖先关系

1 2 3 3 4 4 2 5 5 1

如果吧
第一次出现看做+
第二次出现看做-
那么根节点到某个节点的一条链，是DFS序的一个前缀

欧拉序
1 2 3 2 4 2 1 5 1
最后一个1一般不记录
长度是2n-2
每个点恰好出现度数次

可以用来求LCA，两个点之间深度最浅的点，就是LCA

CF1328E
对于每个询问
第一步对于输入的k个节点，每个节点变为自己的父亲节点
第二步，求出这些节点中最靠右的左端点最靠左的右端点
最靠右的左端点 < 最靠左的右端点 YES
最靠右的左端点 > 最靠左的右端点 NO

P1514 引水入城
无解
假设第一行都建了水站，问最后一行哪些位置无法被覆盖
如果不是无解，那么每个点建水站，能覆盖的区间一定是连续一段，
只需要考虑每个水站覆盖的最靠左的位置，最靠右的位置，用动态规划
贪心即可

如何生成一个合法的解
按退栈顺序

P1333 瑞瑞的木棍
g[s] = g.size();
g[s] 是 s 加入之前的大小，还是加入之后的大小？跟编译器有关

s[4]
((s[0] * base + s[1]) * base + s[2]) * base + s[3]
((s[0] * base ^ s[1]) * base ^ s[2]) * base ^ s[3]

P1341 无序字母对

路还是回路
有向还是无向

for (int i = 1; i <= n; i++) {
if (d[i] & 1) {
if (start == -1) {
start = i;
}
cnt++;
}
}

for (int i = n; i > 0; i--) {
if (d[i] & 1) {
start = i;
cnt++;
}
}

生成方案
按退栈顺序倒着生成

字典序最小的欧拉回路
每次优先DFS标号小的点