首页 > 其他分享 >圆方树

圆方树

时间:2024-10-24 20:58:15浏览次数:3  
标签:dfn int tot add 圆方树 low New

圆方树

前置知识

点双连通分量

以下简称点双连通分量为点双。

定义

设 $G = (V, E)$ 是一个连通无向图,$K$ 是 $G$ 的点双,如果 $K$ 中任意两点 $u, v$ 都有路径相连,则称 $K$ 是 $G$ 的点双。

性质

  1. 两个点双最多有一个公共点,且这个点为割点。
  2. 对于一个点双,它在 DFS 搜索树中 dfn 值最小的点一定是割点或者树根。

求解算法

可以对于第 $2$ 个性质分类讨论。

  1. 当这个点为割点时,它一定是点双连通分量的根,因为一旦包含它的父节点,他仍然是割点。
  2. 当这个点为树根时:
    有两个及以上子树,它是一个割点。只有一个子树,它是一个点双连通分量的根。它没有子树,视作一个点双。

代码见oi-wiki


现在切入正题。

圆方树的定义

对于图中的任意一个点双,将它的每个点连到一个我们新建出来的点上,并删除原来的所有边,这样得出的图称为圆方树。

定义原来图上就有的点叫做圆点,被新建立出来的点叫做方点。

圆方树的性质

  1. 如果原图连通,那么它一定是一颗树。(所以圆方树这个名字非常形象)

  2. 如果一个圆点连接着两及以上个方点,那么它一定是一个割点。

圆方树的构造

下图给出了圆方树的构造过程:

圆方树的构造过程(原图)
圆方树的构造过程(建点)
圆方树的构造过程(连边和删边)

来源 oi-wiki

算法求解

直接利用 Tarjan,在求解边双的同时,进行连边和删边操作即可。

代码实现

实现
void Tarjan(int u) {
	dfn[u] = low[u] = ++ sign;
	st.push(u);
	for (auto v : g[u]) {
		if (!dfn[v]) {
			Tarjan(v);
			low[u] = min(low[u], low[v]);
			if (low[v] == dfn[u]) {
				tot ++ ;
				int y;
				do {
					y = st.top();
					st.pop();
					add(y, tot, New), add(tot, y, New);
				} while (y != v);
				add(u, tot, New), add(tot, u, New);
			}
		} else low[u] = min(low[u], dfn[v]);
	}
}

经典例题

AT_abc318_g

没有多测,直接不可以总司令。

一眼圆方树板题,先构建圆方树,再看 $a$ 到 $c$ 的路径上有没有一个方点能够到达 $b$。

如果不理解,画个图就明白了。

实现
#include <bits/stdc++.h>
using namespace std;

const int N = 4e5 + 10;

int n, m;
int a, b, c;
vector<int> g[N], New[N];
int tot;
int low[N], dfn[N], sign;
stack<int> st;

void add(int a, int b, vector<int> g[]) {
	g[a].push_back(b);
}

void Tarjan(int u) {
	dfn[u] = low[u] = ++ sign;
	st.push(u);
	for (auto v : g[u]) {
		if (!dfn[v]) {
			Tarjan(v);
			low[u] = min(low[u], low[v]);
			if (low[v] == dfn[u]) {
				tot ++ ;
				int y;
				do {
					y = st.top();
					st.pop();
					add(y, tot, New), add(tot, y, New);
				} while (y != v);
				add(u, tot, New), add(tot, u, New);
			}
		} else low[u] = min(low[u], dfn[v]);
	}
}

int pre[N];
bool flag;

void Get_path(int u) {
	if (u == c) {
		flag = true;
		return ;
	}
	for (auto v : New[u]) {
		if (v == pre[u]) continue;
		if (!flag) {
			pre[v] = u;
			Get_path(v);
			if (flag) return ;
		}
	}
}

signed main() {
	cin >> n >> m >> a >> b >> c;
	tot = n;
	while (m -- ) {
		int a, b;
		cin >> a >> b;
		add(a, b, g), add(b, a, g);
	}
	for (int i = 1; i <= n; i ++ )
		if (!dfn[i]) {
			Tarjan(i);
			while (!st.empty()) st.pop();
		}
	Get_path(a);
	int t = c;
	while (t != a) {
		if (t > n) {
			for (auto v : New[t])
				if (v == b) {
					cout << "Yes\n";
					return 0;
				}
		}
		t = pre[t];
	}
	cout << "No\n";
	return 0;
}

P4320 道路相遇

比上面的题难一点,但也不是很难。

显然的,求 $u$ 到 $v$ 必经点的数量就是求 $u$ 到 $v$ 之间圆点的数量。

但是如果还是像上一题一样,直接求出 $u$ 到 $v$ 所经过的点,时间复杂度为 $O(nq)$,无法通过。

考虑优化,因为是求圆点的数量,不妨给每个点都设一个权值,圆点值为 $1$,方点值为 $0$。

所以问题转化成了求 $u$ 到 $v$ 之间权值和。

又因为圆方树是一颗树,使用树上路径差分。

定义 $sum_u$ 为根节点到 $u$ 的路径上的权值和。

那么答案就是 $sum_u + sum_v - 2 * sum_{lca(u, v)} + v_{lca(u, v)}$。

其中 $v_u$ 表示 $u$ 点的权值。

实现
#include <bits/stdc++.h>
using namespace std;

const int N = 5e5 + 10;

int n, m;
vector<int> g[N], New[N * 2];
int tot;
int low[N], dfn[N], sign;
stack<int> st;
int q;

void add(int a, int b, vector<int> g[]) {
	g[a].push_back(b);
}

void Tarjan(int u) {
	dfn[u] = low[u] = ++ sign;
	st.push(u);
	for (auto v : g[u]) {
		if (!dfn[v]) {
			Tarjan(v);
			low[u] = min(low[u], low[v]);
			if (low[v] == dfn[u]) {
				tot ++ ;
				int y;
				do {
					y = st.top();
					st.pop();
					add(y, tot, New), add(tot, y, New);
				} while (y != v);
				add(u, tot, New), add(tot, u, New);
			}
		} else low[u] = min(low[u], dfn[v]);
	}
}

int pre[N * 2];
bool flag;

int fa[N * 2];
int v[N * 2];
int d[N * 2];

void dfs(int u, int father, int dep) {
    fa[u] = father;
    d[u] = dep;
    if (u <= n) v[u] = 1;
    else v[u] = 0;
    for (auto v : New[u]) {
        if (fa[v]) continue;
        dfs(v, u, dep + 1);
    }
}

int dp[N * 2][40];
int f[N * 2][40];

void ST() {
    memset(dp, -1, sizeof dp);
    for (int i = 1; i <= tot; i ++ ) {
        dp[i][0] = fa[i];
    }
    for (int j = 1; j <= log2(tot); j ++ )
        for (int i = 1; i <= tot; i ++ ) {
            dp[i][j] = dp[dp[i][j - 1]][j - 1];
        }
}

int lca(int x, int y) {
	if (d[x] < d[y]) swap(x, y);
	for (int i = 0, len = d[x] - d[y]; i <= log2(tot); i++, len >>= 1) if (len & 1) x = dp[x][i];
	if (x == y) return x;
	for (int i = log2(n); i >= 0; i--) {
		if (dp[x][i] == dp[y][i]) continue;
		x = dp[x][i];
		y = dp[y][i];
	}
	return dp[x][0];
}

int sum[N * 2];

void dfs2(int u, int father) {
	sum[u] = v[u] + sum[father];
	for (auto v : New[u]) {
		if (v == father) continue;
		dfs2(v, u);
	}
}

signed main() {
	// ios::sync_with_stdio(false);
	// cin.tie(0), cout.tie(0);
	cin >> n >> m;
	tot = n;
	while (m -- ) {
		int a, b;
		cin >> a >> b;
		add(a, b, g), add(b, a, g);
	}
	for (int i = 1; i <= n; i ++ )
		if (!dfn[i]) {
			Tarjan(i);
			while (!st.empty()) st.pop();
		}
    dfs(1, -1, 1);
	// for (int i = 1; i <= tot; i ++ )
	// 	cout << i << ": " << fa[i] << " " << d[i] << " " << v[i] << endl;
    ST();
	dfs2(1, -1);
    cin >> q;
    while (q -- ) {
        int a, b;
        cin >> a >> b;
		int LCA = lca(a, b);
		cout << sum[a] + sum[b] - 2 * sum[LCA] + v[LCA] << endl;
    }
	return 0;
}

P4630 [APIO2018] 铁人两项

也比较简单。

本题考察的是对圆方树的点的赋值。

圆点赋为 $-1$,方点赋为当前点双的大小。

然后 DFS 一边,把

标签:dfn,int,tot,add,圆方树,low,New
From: https://www.cnblogs.com/zla2012/p/18500943

相关文章

  • 圆方树学习笔记
    元方树。下文除特殊强调外,所有图皆为无向图。引入割点:在图中,删除某个点后,导致图不再连通的点。点双连通:在一张图中,取两个点\(u\)、\(v\),无论删去哪个点(除\(u\)、\(v\)自身外),\(u\)、\(v\)都能连通,我们就说\(u\)和\(v\)点双连通。点双连通分量(后文称点双):对于一个无向......
  • 圆方树学习笔记
    前置芝士边双连通与点双连通oi-wiki上是这样说的:在一张连通的无向图中,对于两个点\(u\)和\(v\),如果无论删去哪条边(只能删去一条)都不能使它们不连通,我们就说\(u\)和\(v\)边双连通。在这里我们需要得出一个非常重要的性质:边双连通具有传递性。通俗来说,就是当\([x,y]\)......
  • 圆方树
    小粉兔圆方树兔已经讲的非常好了,我就讲我的理解吧!!!大多数情况下,图论是比树结构要复杂多的,所以引入了一个圆方树的一种数据结构。把无向图转化为由原点与点双连通分量组成的树,原图的每一个点都是一个圆点,每一个点双都是一个方点,所以形成的新图有\(n+c\)个点,每个点双转为方点时......
  • 圆方树
    点双联通分量:对一张图,若其不含割点,则其为一个点双。1,对于点双中的两个点(除只有两点一边的特殊图),可以视作其必然存在两条不同的简单路径,使两者经过的并集为空。2,对于点双中任意一对点,经过它们的简单路径的并集一定为点双本身,意即可以认为两点间简单路径可以通过点双内任意一点。......
  • 圆方树
    定义割点:无向图中,若删除点及其连边,连通块变多,那么被删除的点为割点点双连通:若无向图中点对\(x,y\),删除任意非\(x\)和非\(y\)节点后,\(x\)和\(y\)任然连通,陈\(x,y\)点双连通点双连通子图:无向图中的一个子图\(G\),\(G\)中任意2点都是联通的,那么称\(G\)为原图的点双......
  • 圆方树学习笔记 & 最短路 题解
    前言圆方树学习笔记,从一道例题讲起。题目链接:Hydro&bzoj。题意简述仙人掌上求两点距离。题目分析为了把仙人掌的性质发挥出来,考虑将其变成一棵树。圆方树就是这样转换的工具。先讲讲圆方树的概念:原图上的点为圆点,每个点双对应一个方点,树边都是方点连向点双内的圆点。具......
  • 圆方树
    定义圆方树:将无向图转化为树形结构的数据结构,使得树上2点路径上的点都是原图的必经点。圆点:原无向图\(G\)中的点,仍然保留在圆方树中,称之为圆点。方点:将每一个点双连通分量新建一个“方点”。树边:每一个方点都向对应的点双内的圆点连边。基本性质:性质一:圆方树的总点数=......
  • 圆方树
    一些概念割点:无向图中,若删除点x及其连边,连通块变多,那么x为割点。点双连通:若点对x和y,删除任意非x和非y节点后,x和y仍然联通,称x和y点双连通。点双联通子图:无向图中的一个子图G,G中任意两点都是点双连通的,那么G为原图的一个点双连通子图。点双联通分量:无向图中的极大点双联通子图......
  • 【算法学习】圆方树——处理仙人掌的利器
    圆方树大概分两种,一个是圆方树,一个是广义圆方树。圆方树这可以解决仙人掌上的问题。任意一条边至多只出现在一条简单回路的无向连通图称为仙人掌。很多题解将其作为无向图构建,本文将其构建为外向树,在这个问题中两种构建方式不会影响求解。构建方式记读入的图为原图,构建的......
  • 圆方树
    圆方树这里的圆方树指广义圆方树。对于一张\(n\)个点的无向图,其中包含\(k\)个点双,那么这张图建出的圆方树一共有\(n+k\)个点,其中前\(n\)个点为原图中的点,称为圆点,后\(k\)个点每个点代表一个点双,称为方点,每个点双与其中包含的点连边构成一个菊花,这\(k\)个菊花经由图......