基环树学习笔记

前言

emmmm,没有什么想要说的

算法概述

基环树啊,经过我粗浅的学习,认为它是将环和树边分开处理,具体来说就是每次强制断掉环中的任意一条边来处理。(我觉得说不上算法,可能只是一种数据结构或者巧妙的思想?

反正就是很妙啊。。。

定义

基环树,也是环套树,一种有 \(n\) 个点 \(n\) 条边 的图, 即在一棵 \(n\) 个点的树的基础上在任意两点(没有直接连边)之间在连上一条边的图。

可能有点抽象其实还好,看看下面我盗的图吧(

  • 无向树

基环树学习笔记

  • 外向树

基环树学习笔记

  • 内向树

基环树学习笔记

所以基环树的性质不多,根据上面我们就可以得到最显然的一条:

  • 点数与边数相同。

基环树学习笔记就这?!

对没错,就这(

前置知识

拓扑排序

用来处理无向图,找到环上的每一个点啦。

基本流程:

  • 找到入度为 \(1\) 的点入队
  • 每次取出队首,将与队首相连的所有点的入度分别减 \(1\)
  • 重复以上操作,知道队列为空

\(Code:\)


void t_sort() {
	int l = 0, r = 0, now, ver;
	for(int i = 1; i <= n; i ++) {
		if(in[i] == 1) sta[++r] = i;
	}
	while(l < r) {
		now = sta[++l];
		for(int i = head[now]; i; i = e[i].nex) {
			ver = e[i].to;
			in[ver] --;
			if(in[ver] == 1) sta[++r] = i;
		}
	}
}

这样处理之后,按理来说所有点的入度都应该 \(\le\) \(1\), 但是因为有环,所以存在入度 \(\ge\) \(1\)。

所以在拓扑之后,再搜一遍,入度 \(\ge\) \(1\) 的都是环上的点, 就找到整个环的位置啦~

DFS

这个没什么要讲的。

\(Code:\)

void dfs(int x) {
	int ver;
	sta[++cnt] = x, vis[x] = 1;
	for(int i = head[x]; i; i = e[i].nex) {
		ver = e[i].to;
		if(rel[x][ver] || vis[ver]) continue;
		dfs(ver);
	}
}

注意: \(dfs\) 的代码并没有模板化,上面给出的代码仅仅只是为了介绍 \(dfs\),并不是用于所有的基环树。具体实现要看题目要求而定。

应用

断环法

应该算是最常见的方法吧?

顾名思义,断环法其实就是每次通过断掉环上任意一条边,使其变成一棵 \(n - 1\) 条边的树,在树上跑一遍答案。最后取满足条件的最大值或者最小值。

这样感觉就是暴力嘛,所以只适用于数据范围很小而且环的存在(也就是断掉环上的一条边之后)不会影响答案的情况。

经典例题[NOIP2018 提高组] 旅行

题目大意:在一个连通的 \(n\) 个点 \(n - 1\) 或者 \(n\) 条边的无向图上,从任意一点出发,沿边遍历每一个点,求字典序最小的遍历顺序。

二次dp法

断环复制法

总结

总的来说,基环树还是很巧妙滴~

一般基环树的题都有很明显的特征,要么就是题面直接告诉你这是一棵基环树,要么就是描述为“ \(n\) 点 \(n\) 条边 无重边无自环保证联通”……

这个时候

参考博客

上一篇:python TCP Socket的粘包和分包的处理详解


下一篇:【邻接表】72 邻接表:删除一个顶点