基础图论

发表于 更新于 阅读次数： 本文字数： 4.5k 阅读时长 ≈ 16 分钟

基础图论

基本定义

约定

约定 G=(V,E)G = (V, E) 表示点集为 VV，边集为 EE 的图，若无特殊说明，则 ∣V∣=n|V| = n，∣E∣=m|E| = m。

若干基本定义：

  • 边导出子图：选出若干条边，以及这些边所连接的所有顶点组成的图称为边导出子图；
  • 点导出子图：选出若干个点，以及两端都在该点集的所有边组成的图称为点导出子图；
  • 闭合子图：点集 VV 导出的闭合子图是所有 VV 可达的点的点导出子图，即：若 xx 在子图内，则 xx 的所有出边和出点均在子图内的原图子图；等价于每个点能到的所有点都在子图中；
  • kk 正则图：若一个无向图每个点的度数均为 kk，则称其为 kk 正则图。

DFS 树

当 dfs 一个图时，按照 dfs 的顺序可以构造出一个树结构，被称为 DFS 树。

有向图的 dfs 树主要有四种边：

  • 树边：每次搜索找到一个还没有访问过的结点的时候就形成了一条树边。
  • 反祖边：也叫回边，即指向祖先结点的边。
  • 横叉边：在 dfs 树中从一个子树中的结点指向另一个子树中的结点的边，即除了其余三种边的边，表示遇到了一个已经访问过的结点，但这个结点并不是它的祖先。
  • 前向边：在 dfs 树中从一个深度小的结点指向一个深度大的结点的边，不包括树边，表示遇到了子树中的结点。

若干由 DFS 树导出的序列

在每个节点入栈时将其记录下来形成的序列称为 dfs 序，这是一种将树形结构映射为线性结构的方法；

在构造题中，通常我们用到的是无向图的 DFS 树。如果我们将每条边按照第一次经过时的方向进行定向，则无向图的 DFS 树满足所有非树边都是后向边。

对这棵 dfs 树进行访问，每到达一个点就将其编号记录下来，形成的长度为 2n−12n-1 的序列称为欧拉序，若将结点 uu 第一次在欧拉序中出现的位置记为 pos⁡(u)\operatorname{pos}(u)，欧拉序记为 E[1,2n−1]E[1, 2n-1]，则有

pos⁡(LCA⁡(u,v))=min⁡{pos⁡(k)∣k∈E[pos⁡(u),pos⁡(v)]}\operatorname{pos}(\operatorname{LCA}(u, v)) = \min\left\{\operatorname{pos}(k) \mid k \in E\left[\operatorname{pos}(u), \operatorname{pos}(v)\right]\right\}

此时我们将一个不带修改的 LCA 问题转换为了求区间最小的 RMQ 问题，若使用 ST 表等数据结构进行解决，预处理时间为 O(nlog⁡n)\mathcal O(n \log n)，单次查询时间为 O(1)\mathcal O(1)，称为 O(nlog⁡n)−O(1)\mathcal O(n \log n)-\mathcal O(1) LCA。

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
int dfn[mmax << 1], pos[mmax], tot = 0;

void dfs(int cur)
{
    dfn[++tot] = cur;
    pos[cur] = tot;
    for(auto v: edge[cur])
    	if(!pos[v])
        	dfs(v), dfn[++tot] = cur;
}

// st[i][j] -> range [i, i + 2^j - 1]
void pre()
{
    Log[0] = -1;
    for(int i = 1;i <= (n << 1);i++)
        Log[i] = Log[i >> 1] + 1;
    for(int i = 1;i <= (n << 1) - 1;i++)
        st[0][i] = dfn[i];
    for(int i = 1;i <= Log[(n << 1) - 1];i++)
        for(int j = 1;j + (1 << (i - 1)) <= ((n << 1) - 1);j++)
            st[i][j] = pos[st[i - 1][j]] < pos[st[i - 1][j + (1 << (i - 1))]]
            			? st[i - 1][j] : st[i - 1][j + (1 << (i - 1))];
}

int find(int u, int v)
{
    // u = pos[u], v = pos[v]
    assert(u <= v);
    int x = Log[v - u + 1];
    return pos[st[x][u]] < pos[st[x][v - (1 << x) + 1]] ? st[x][u] : st[x][v - (1 << x) + 1];
}

最短路

Bellman-Ford

称一轮松弛为对于每一条边 (u,v)(u, v)，用 disu+wu,vdis_u + w_{u, v} 更新 disvdis_v。我们可以断言每轮至少有一个节点的最短路被更新，松弛 n−1n - 1 轮即可。

正确性证明：设源点为 1，在 1→u1\to u 的最短路中一定会经过 1→i1\to i 的最短路，其中 ii 是 uu 的某个前驱结点，所以一个节点的最短路必定可以通过另一个节点的最短路扩展而来。由于最长的最短路最多只会包含 n−1n - 1 条边，而第 ii 次松弛可以得到包含 ii 条边的最短路，故最多只需松弛 n−1n - 1 轮。

通过此性质可以来判断一个图是否含有负环，如果在第 nn 轮松弛中仍然有节点的最短路被更新，那么这张图必定有负环存在。时间复杂度为 O(nm)\mathcal O(nm)。

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
bool check(int s)
{
    constexpr int inf = 0x3f3f3f3f; 
    std::vector dis(n + 1, inf);
    dis[s] = 0;
    for(int _ = 1;_ < n;_++)
    {
        for(auto [u, v, w]: edge)
        {
            if(dis[u] != inf && dis[u] + w < dis[v])
            {
                dis[v] = dis[u] + w;
            }
        }

    }
    for(auto [u, v, w]: edge)
    {
        if(dis[u] == inf || dis[v] == inf)
            continue;
        if(dis[u] + w < dis[v])
            return false;
    }
    return true;
}

Dijkstra

DSU on tree

众所周知，dsu 是并查集，但 dsu on tree 不是树上并查集，而是树上启发式合并。

启发式合并

启发式合并泛指将一个小的集合合并到一个大的集合中的方法。

初始时你有 nn 个集合，其中 si={i}s_i = \left\{i\right\}。每次可以执行合并操作，即选定两个集合 sxs_x，sys_y，令 sx=sx⋃sys_x = s_x \bigcup s_y，sy=∅s_y = \varnothing。如此合并 n−1n - 1 次后只会剩下 1 个集合。请维护每次合并后的集合。

显然这个问题可以通过并查集进行维护，但并查集只对两个集合中的元素进行了标记，而没有实在地将两个集合合并。

另一种方法是暴力模拟合并的过程：

1
2
3
4
5
6
7
for(int y = 1;y < n;y++)
{
    int x = y + 1;
    for(auto z: s[y])
    	s[x].insert(z);
	s[y].clear();
}

注意到暴力的过程中，每次都会有 O(n)\mathcal O(n) 个元素要向后合并，时间复杂度为 O(n2)\mathcal O(n^2) 的，不能接受。

考虑暴力合并的过程中，把大的集合合并到小的集合里是很亏的，会多加一部分无谓的时间开销，所以考虑每次合并时将小的并到大的里面去：

1
2
3
4
5
6
7
8
if(siz[x] > siz[y])
    std::swap(x, y);
assert(siz[x] <= siz[y]);
for(auto z: s[x])
    s[y].insert(z);
siz[y] += siz[x];
siz[x] = 0;
s[x].clear();

分析一下复杂度？结论为 O(nlog⁡n)\mathcal O(n \log n)。

考虑每个元素对时间复杂度的贡献，即考虑把 nn 个集合合并到 1 个集合的过程中每个元素会被移动多少次。

假设小集合为 sxs_x，大集合为 sys_y，合并后大集合的大小变为 ∣sx⋃sy∣\left|s_x \bigcup s_y\right|，又由于小集合并到大集合中，于是 ∣sx∣≤∣sy∣|s_x| \leq |s_y|，故合并后的集合大小至少为 2∣sx∣2|s_x|，也即操作一次后集合大小至少变为小集合的两倍。由于元素个数为 O(n)\mathcal O(n)，故每个元素最多被操作 O(log⁡n)\mathcal O(\log n) 次，于是时间复杂度为 O(nlog⁡n)\mathcal O(n \log n)。

example1：P3201 [HNOI2009] 梦幻布丁

image-20230520155522733

首先考虑如何统计答案：可以通过一次循环判断 a[i] != a[i+1]，如果成立则段数 +1，时间复杂度为 O(n)\mathcal O(n)。

再考虑修改一个点的颜色时段数会如何变化：先考虑这个点与左右两段的颜色是否一致，再考虑修改颜色后这个点与左右两段的颜色是否一致，时间复杂度为 O(1)\mathcal O(1)。

考虑 1 操作，本质上为把 xx 集合合并到 yy 中，注意到有多少段本质上和每段的具体颜色是没有关系的，即 1 2 2 1 和 3 4 4 3 均为三段，这使得将 xx 合并到 yy 和将 yy 合并到 xx 是等价的，所以此时可以使用启发式合并了！但考虑到合并时还是需要通过实际颜色进行合并，于是还需要记录每个集合的实际颜色是什么。

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
void solve()
{
	std::cin >> n >> m;
	for(int i = 1;i <= n;i++)
	{
		std::cin >> a[i];
		pos[a[i]].emplace_back(i);
	}
	for(int i = 1;i <= n + 1;i++) // 把 0 和 n+1 一块考虑进来，就不用考虑边界情况了
		Ans += (a[i] != a[i - 1]);
	auto modify = [&](int pos, int col) -> void
	{
		Ans -= (a[pos] != a[pos - 1]) + (a[pos] != a[pos + 1]);
		a[pos] = col;
		Ans += (a[pos] != a[pos - 1]) + (a[pos] != a[pos + 1]);
	};
	for(int i = 1;i <= m;i++)
	{
		int op;
		std::cin >> op;
		if(op == 2)
			std::cout << Ans - 1 << endl; // 注意一定要减一 因为上面把 0 和 n+1 考虑进来了
		else
		{
			int x, y;
			std::cin >> x >> y;
			if(x == y)
				continue;
			if(pos[x].size() > pos[y].size())
				std::swap(pos[x], pos[y]);
			assert(pos[x].size() <= pos[y].size()); // 用来判断自己有没有反向启发式（
			if(pos[y].empty())
				continue;
			int col = a[pos[y][0]];
			// x 和 y 都不一定是大集合的颜色 由于 pos[x] 和 pos[y] 有可能交换过
			// 但 a[pos[y][0]] 一定是 
			for(auto z: pos[x])
			{
				modify(z, col);
				pos[y].emplace_back(z);
			}
			pos[x].clear();
		}
	}
}

image-20230520173210776

怎么和启发式合并扯上关系的？假设初始时一张图上只有 nn 个孤立点，接着把所有的边从大到小排序，每次依次加入这些边，相当于把两个点集合并起来。

考虑每个询问，如果询问的两点在两个不相同的集合中，那么答案即为当前加入的这条边。由于边被从大到小排序，故正确性显然；于是启发式维护点集，当一个询问的两个端点在两个不同的点集时即为答案，若在同一点集时则继续进行合并操作，直到不在同一点集。

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
constexpr int mmax = 2E5 + 10;

std::array<int, 3> edge[mmax];
std::array<int, 2> Q[mmax];
std::set<int> vec[mmax];
std::vector<int> f, Ans;
std::map<int, int> que[mmax];

int find(int x) {return f[x] == x ? x : f[x] = find(f[x]);}

int main()
{
	#ifdef ONLINE_JUDGE
	ioclear;
	#endif

	int n, q;
	std::cin >> n >> q;
	f.resize(n + 1);
	Ans.resize(n + 1);
	for(int i = 1;i < n;i++)
		std::cin >> edge[i][1] >> edge[i][2] >> edge[i][0];
	std::sort(edge + 1, edge + n);
	std::reverse(edge + 1, edge + n);
	for(int i = 1;i <= n;i++)
		vec[i].insert(i), f[i] = i;
	for(int i = 1;i <= q;i++)
	{
		std::cin >> Q[i][0] >> Q[i][1];
		que[Q[i][0]][i] = Q[i][1];
		que[Q[i][1]][i] = Q[i][0];
	}
	for(int i = 1;i < n;i++)
	{
		int u = find(edge[i][1]), v = find(edge[i][2]);
		// if(u == v) continue;
		if(vec[u].size() > vec[v].size())
			std::swap(u, v);
		assert(vec[u].size() <= vec[v].size());
		for(auto [id, w]: que[u])
		{
			if(vec[v].count(w))
			{
				Ans[id] = edge[i][0];
				que[v].erase(id);
			}
			else
				que[v][id] = w;
		}
		que[u].clear();
		for(auto w: vec[u])
			vec[v].insert(w);
		f[u] = v;
	}
	for(int i = 1;i <= q;i++)
		std::cout << Ans[i] << endl;
}

但是这样很慢！完全跑不过倍增！考虑哪里会导致时间爆炸：

std::set 和 std::map 自带一个 log⁡\log，换成 std::unordered_set 和 std::unordered_map 也不好使，有没有办法不用？

  • 注意到 std::set 是为了记录每个点对应的点集中有哪些点的，为了保证唯一性，我们可以再开一个数组 belong[i] 表示点 i 属于哪个点集，于是 vec[v].count(w) 可以顺利地更改为 belong[w] == v，去掉了一个 std::set；
  • 再注意到 std::map 是记录每个点集中离线下来的查询的，上面的做法是每当完成一个查询，就去对应的另一个点集中去掉这个查询。注意到此处并不需要真正地去掉对应的查询，只要保证在再次遍历到这个查询时不再对答案进行更新即可，于是可以直接判断 Ans[id] != 0 是否成立，如果成立则此次查询跳过，于是我们就把 std::map 去掉啦！
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
constexpr int mmax = 2E5 + 10;
using pii = std::pair<int, int>;

std::array<int, 3> edge[mmax];
std::array<int, 2> Q[mmax];
std::vector<int> f, Ans, vec[mmax], belong;
std::vector<pii> que[mmax];

int find(int x) {return f[x] == x ? x : f[x] = find(f[x]);}

int main()
{
	#ifdef ONLINE_JUDGE
	ioclear;
	#endif

	int n, q;
	std::cin >> n >> q;
	f.resize(n + 1);
	Ans.resize(n + 1);
	belong.resize(n + 1);
	for(int i = 1;i < n;i++)
		std::cin >> edge[i][1] >> edge[i][2] >> edge[i][0];
	std::sort(edge + 1, edge + n);
	std::reverse(edge + 1, edge + n);
	for(int i = 1;i <= n;i++)
		vec[i].emplace_back(i), f[i] = i, belong[i] = i;
	for(int i = 1;i <= q;i++)
	{
		std::cin >> Q[i][0] >> Q[i][1];
		que[Q[i][0]].emplace_back(i, Q[i][1]);
		que[Q[i][1]].emplace_back(i, Q[i][0]);
	}
	for(int i = 1;i < n;i++)
	{
		int u = find(edge[i][1]), v = find(edge[i][2]);
		// if(u == v) continue;
		if(vec[u].size() > vec[v].size())
			std::swap(u, v);
		assert(vec[u].size() <= vec[v].size());
		for(auto [id, w]: que[u])
		{
			if(Ans[id]) continue;
			if(belong[w] == v)
				Ans[id] = edge[i][0];
			else
				que[v].emplace_back(id, w);
		}
		for(auto w: vec[u])
			vec[v].emplace_back(w), belong[w] = v;
		que[u].clear();
		vec[u].clear();
		f[u] = v; // must u into v
	}
	for(int i = 1;i <= q;i++)
		std::cout << Ans[i] << endl;
}

image-20230520190210067

有扫描线做法，此处不表。

看起来和启发式合并没关系！考虑分治：如果序列 {A}\left\{A\right\} 是好的，那么对于整个区间，必然存在一个元素 xx 仅出现了一次，于是所有包含 xx 的区间都是好的，于是此时只需要递归检查 xx 的左侧区间和右侧区间是不是好的即可。

如何检查一个数 xx 只在区间 [l,r][l, r] 里出现了一次？通过两个数组 pre[x] 和 nxt[x] 表示 xx 的上一次和下一次的出现位置，若不存在则 pre[x]=0，nxt[x]=n+1，当 pre[x]<l && nxt[x]>r 成立时则代表 xx 在 [l,r][l, r] 中仅出现了一次。

时间复杂度是不是对的？如果直接分治则时间复杂度是无法保证的：当每次找到的 xx 都很靠后，则找到这个 xx 就需要 O(n)\mathcal O(n) 的时间，同时递归下去的区间会非常不均匀，极端情况下每次分治只能分掉一个元素，此时的时间复杂度为 O(n2)\mathcal O(n^2)，无法接受。

考虑一种新东西：启发式分治！对于上面提到的导致时间复杂度爆炸的问题，倒着找 xx 不就好了？但是又会出现 xx 很靠前导致时间复杂度爆炸的问题，于是把两种枚举方法结合一下，从区间两侧往中间枚举分治点即可。

时间复杂度看起来不像是正确的？令 T(n)\mathcal T(n) 表示解决规模为 nn 的问题时的时间复杂度，xx 为分治点，则 T(n)=T(x)+T(n−x)+O(min⁡(x,n−x))\mathcal T(n) = \mathcal T(x) + \mathcal T(n - x) + \mathcal O(\min(x, n - x))，其中 O(min⁡(x,n−x))\mathcal O(\min(x, n - x)) 表示找到分治点 xx 的时间复杂度。

结论：T(n)=O(nlog⁡n)\mathcal T(n) = \mathcal O(n \log n)。

上式和启发式合并的时间复杂度是等价的，由于上式也可表示为合并出大小为 xx 的集合的时间复杂度，加上合并出大小为 n−xn - x 的集合的时间复杂度，再加上把这两个集合合并起来的时间复杂度，由于把两个集合合并是将小集合合并到大集合里，于是启发式合并和启发式分治的时间复杂度一致，为 O(nlog⁡n)\mathcal O(n \log n)。

这同时表明，只要分治时，本区间分治的代价只跟短的一侧区间有关，那么时间复杂度就为 O(nlog⁡n)\mathcal O(n \log n)。

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
void solve()
{
    int n;
    std::cin >> n;
    std::vector<int> a(n + 1), pre(n + 1), nxt(n + 1);
    for(int i = 1;i <= n;i++)
        std::cin >> a[i];
    std::map<int, int> pos;
    for(int i = 1;i <= n;i++)
    {
        if(pos.count(a[i]))
            pre[i] = pos[a[i]];
        else
            pre[i] = 0;
        pos[a[i]] = i;
    }
    pos.clear();
    for(int i = n;i >= 1;i--)
    {
        if(pos.count(a[i]))
            nxt[i] = pos[a[i]];
        else
            nxt[i] = n + 1;
        pos[a[i]] = i;
    }
    auto dfs = [&](auto &&f, int l, int r) -> bool
    {
        if(l > r)
            return true;
        for(int i = l, j = r;i <= j;i++, j--)
        {
            if(pre[i] < l && nxt[i] > r)
                return f(f, l, i - 1) && f(f, i + 1, r);
            if(pre[j] < l && nxt[j] > r)
                return f(f, l, j - 1) && f(f, j + 1, r);
        }
        return false;
    };
    if(dfs(dfs, 1, n))
        std::cout << "non-boring\n";
    else
        std::cout << "boring\n";
}

DSU on tree

dsu on tree 是为了维护子树信息的一种方法。

给定一棵树，每个节点有不同的颜色，给若干询问，每次询问以 xx 为根的子树中有多少种不同的颜色。

做法很多！比如可以搞出 dfs 序转成序列问题，可以用莫队等一系列的方法。

对于每个节点开一个 std::set，表示以它为根的子树中都有哪些颜色，考虑合并两个子树，此时需要把两个颜色集合合并，可以使用启发式合并的做法，把小子树的集合合并到大子树的集合里，再将子树的根合并进去即可。

如果将启发式合并的过程画成一个树形结构，事实上也是一种 dsu on tree。但 dsu on tree 有更加好写且常数小的做法：对于每个点，我们都找到它的重儿子，把当前结点合并到重儿子的集合中，再将各个轻儿子也合并进去。

注意到合并各个轻儿子需要 for 所有轻儿子集合中的元素，我们可以将其转换为直接访问所有轻儿子集合中的结点。也即我们不需要保存每个轻儿子对应的集合，此时对应的，我们需要 for 轻儿子子树中的所有结点即可。

看起来很暴力！但本质上还是启发式合并，即将小的东西往大的东西里面合并。

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
std::array<int, N> l, r, id, siz, hs;
int tot;

void dfs1(int u, int fa)
{
    l[u] = ++tot;
    id[tot] = u;
    siz[u] = 1;
    hs[u] = -1;
    for(auto v: edge[u])
    {
        if(v == fa)
            continue;
        dfs1(v, u);
        siz[u] += siz[v];
        if(hs[u] == -1 || siz[v] > siz[hs[u]])
            hs[u] = v;
    }    
    r[u] = tot;
    return;
}

void dfs2(int u, int fa, bool keep)
{
    for(auto v: edge[u])
        if(v != fa && v != hs[u])
            dfs2(v, u, false);
    // 处理重儿子
    if(hs[u] != -1)
        dfs2(hs[u], u, true);
    for(auto v: edge[u])
    {
        if(v != fa && v != hs[u]) // v 是轻儿子
        {
            for(int x = l[v];x <= r[v];x++) // 把 v 子树中所有点加入重儿子集合中
                add(id[x]);
        }
    }
    add(u); // 把 u 加入重儿子集合中
    if(!keep)
    {
        // 清空轻儿子的贡献
        for(int x = l[u];x <= r[u];x++)
            del(id[x]);
    }
}

参考资料

初级图论 - qAlex_Weiq - 博客园 (cnblogs.com)

高级图论 - qAlex_Weiq - 博客园 (cnblogs.com)

「学习笔记」图论基础 | do_while_true’s blog (do-while-true.github.io)

图论部分简介 - OI Wiki

代码源