「学习笔记」基环树

众所周知，一棵有 \(n\) 个节点的树有 \(n - 1\) 条边，树上没有环。
据此，明显的，对于一个有 \(n\) 个结点 \(n\) 条边的无向连通图，必定是在一棵树上的任意两个节点之间连一条边构成的。我们把 \(n\) 个节点 \(n\) 条边的无向连通图，就称为基环树。

基环树上存在环，因此基环树它不是树，而是图。基环树又称章鱼图。

如图，这就是一棵基环树。
如果一张有向弱连通图每个点的入度都为 \(1\)，则称它是一棵 基环外向树，如下图。

如果一张有向弱连通图每个点的出度都为 \(1\)，则称它是一棵 基环内向树，如下图。

多棵树可以组成一个森林，多棵基环树可以组成基环森林，多棵基环外向树可以组成基环外向树森林，多棵基环内向树可以组成基环内向森林。

找环#

基环树的的特别之处就在于这个环，因此，大部分基环树题目中，找环是十分必要的。
在简单图中，可以利用 dfs 的天然栈性质来找环，具体实现方式与 tarjan 求强连通分量很相似。

void getloop(int u) {
	dep[u] = dep[fa[u]] + 1;
	for (int v : e[u]) {
		if (v == fa[u])	continue ;
		if (!dep[v]) {
			fa[v] = u;
			getloop(v);
		}
		else if (dep[v] < dep[u]) {
			for (int i = u; ; i = fa[i]) {
				ok[i] = 1;
				loop[++ m] = i;
				if (i == v) {
					break;
				}
			}
		}
	}
}

再有重边的图中，需要做一下小小的处理，与 tarjan 求双连通分量很像，记录一下边的编号，只要不走回刚走过来的边就行。

vector<pair<int, int> > e[N];

void getloop(int u, int i) {
	dep[u] = dep[fa[u]] + 1;
	for (auto it : e[u]) {
		int v = it.first, k = it.second;
		if (k == i)	continue;
		if (!dep[v]) {
			fa[v] = u;
			getloop(v, k);
		}
		else if (dep[v] < dep[u]) {
			for (int j = u; ; j = fa[j]) {
				ok[j] = 1;
				loop[++ m] = j;
				if (i == v) {
					break;
				}
			}
		}
	}
}

练习#

基环树题目中，较常见的 套路 思路就是先将环去掉，对每一棵树做处理，最后再对环做处理。

P8943 Deception Point#

这是一道基础的入门题。
我们发现，只要两个人能在到达环上之前不碰面（包括刚到达环上），那雷切尔就一定存活 秦王绕柱，否则就必死无疑，处理三角洲到达环上的距离与雷切尔到达环上的距离，再查看是否会在到达环上是碰面即可。

/*
  The code was written by yifan, and yifan is neutral!!!
 */

#include 
using namespace std;
typedef long long ll;

template<typename T>
inline T read() {
	T x = 0;
	bool fg = 0;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		fg |= (ch == '-');
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = (x << 3) + (x << 1) + (ch ^ 48);
		ch = getchar();
	}
	return fg ? ~x + 1 : x;
}

const int N = 2e5 + 5;

int n, q, m;
int dep[N], top[N], fa[N], loop[N], dis[N];
bool ok[N];
vector<int> e[N];

void getloop(int u) {
	dep[u] = dep[fa[u]] + 1;
	for (int v : e[u]) {
		if (v == fa[u])	continue ;
		if (!dep[v]) {
			fa[v] = u;
			getloop(v);
		}
		else if (dep[v] < dep[u]) {
			for (int i = u; ; i = fa[i]) {
				ok[i] = 1;
				loop[++ m] = i;
				if (i == v)	break;
			}
		}
	}
}

void dfs(int u, int fat, int tp) {
	top[u] = tp;
	for (int v : e[u]) {
		if (v == fat || ok[v])	continue ;
		dep[v] = dep[u] + 1;
		dfs(v, u, tp);
	}
}

int main() {
	n = read<int>(), q = read<int>();
	for (int i = 1, x, y; i <= n; ++ i) {
		x = read<int>(), y = read<int>();
		e[x].emplace_back(y);
		e[y].emplace_back(x);
	}
	getloop(1);
	memset(dep, 0, sizeof dep);
	for (int i = 1; i <= m; ++ i) {
		dfs(loop[i], 0, i);
//		cout << loop[i] << ' ';
	}
	while (q --) {
		int x = read<int>(), y = read<int>();
		int d1 = dep[x], t1 = top[x];
		int d2 = dep[y], t2 = top[y];
		if (d2 + min(abs(t1 - t2), m - abs(t1 - t2)) > d1) {
			puts("Survive");
		}
		else {
			puts("Deception");
		}
	}
	return 0;
}

P8655 [蓝桥杯 2017 国 B] 发现环#

简单的找环模板 = =||

/*
  The code was written by yifan, and yifan is neutral!!!
 */

#include 
using namespace std;
typedef long long ll;

template<typename T>
inline T read() {
	T x = 0;
	bool fg = 0;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		fg |= (ch == '-');
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = (x << 3) + (x << 1) + (ch ^ 48);
		ch = getchar();
	}
	return fg ? ~x + 1 : x;
}

const int N = 1e5 + 5;

int n;
int dep[N], fa[N];
bool ok[N];
vector<int> e[N];

void getloop(int u) {
	dep[u] = dep[fa[u]] + 1;
	for (int v : e[u]) {
		if (v == fa[u])	continue;
		if (!dep[v]) {
			fa[v] = u;
			getloop(v);
		}
		else if (dep[v] < dep[u]) {
			for (int i = u; ; i = fa[i]) {
				ok[i] = 1;
				if (i == v)	break;
			}
		}
	}
}

int main() {
	n = read<int>();
	for (int i = 1, x, y; i <= n; ++ i) {
		x = read<int>(), y = read<int>();
		e[x].emplace_back(y);
		e[y].emplace_back(x);
	}
	getloop(1);
	for (int i = 1; i <= n; ++ i) {
		if (ok[i]) {
			printf("%d ", i);
		}
	}
	return 0;
}

P6037 Ryoku 的探索#

朴素做法为 \(O_{n^2}\) 的。
但仔细观察，就会发现，最终答案一定是除去环上一条边，其他边的长度总和，删掉哪条边呢？根据美观度来判断。

/*
  The code was written by yifan, and yifan is neutral!!!
 */

#include 
using namespace std;
typedef long long ll;

template<typename T>
inline T read() {
	T x = 0;
	bool fg = 0;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		fg |= (ch == '-');
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = (x << 3) + (x << 1) + (ch ^ 48);
		ch = getchar();
	}
	return fg ? ~x + 1 : x;
}

const int N = 1e6 + 5;

int n, m;
ll ans, sum;
int loop[N], top[N], fa[N], dep[N];
ll dis[N];
bool ok[N];

struct node {
	int v;
	ll w, p;
	
	node(int a, ll b, ll c): v(a), w(b), p(c) {};
};

vector<node> e[N];

void getloop(int u) {
	dep[u] = dep[fa[u]] + 1;
	for (node it : e[u]) {
		int v = it.v;
		if (v == fa[u])	continue;
		if (!dep[v]) {
			fa[v] = u;
			getloop(v);
		}
		else if (dep[v] < dep[u]) {
			for (int i = u; ; i = fa[i]) {
				ok[i] = 1;
				loop[++ m] = i;
				if (i == v)	break;
			}
		}
	}
}

void dfs(int u, int fat, int tp) {
	top[u] = tp;
	for (node it : e[u]) {
		int v = it.v;
		ll w = it.w;
		if (v == fat || ok[v])	continue;
		ans += w;
		dfs(v, u, tp);
	}
}

int main() {
	n = read<int>();
	for (int i = 1, x, y; i <= n; ++ i) {
		x = read<int>(), y = read<int>();
		ll w = read<ll>(), q = read<ll>();
		e[x].emplace_back(y, w, q);
		e[y].emplace_back(x, w, q);
	}
	getloop(1);
	for (int i = 1; i <= m; ++ i) {
		dfs(loop[i], 0, loop[i]);
	}
	loop[m + 1] = loop[1];
	for (int i = 1; i <= m; ++ i) {
		for (node it : e[loop[i]]) {
			int v = it.v;
			if (v == loop[i + 1]) {
				dis[i] = it.w;
				sum += it.w;
				break;
			}
		}
	}
	for (int i = 1, u; i <= n; ++ i) {
		u = top[i];
		ll W = 0, P = 1e9;
		for (node it : e[u]) {
			int v = it.v;
			ll w = it.w, p = it.p;
			if (!ok[v])	continue;
			if (p < P) {
				W = w;
				P = p;
			}
		}
		printf("%lld\n", sum - W + ans);
	}
	return 0;
}