图上简单路径问题——转化为圆方树问题：abc318_g

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132645934

https://atcoder.jp/contests/abc318/tasks/abc318_g

对原图建圆方树后，任意两点间的简单路径必然为其树上路径上方点对应其边双的点。

然后判断A，C路径上的方点是否会有B

在这里插入图片描述

圆方树：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void dfs(int x) {
	dfn[x]=low[x]=++tot; z.push(x); 
	for(int y : T[x]) {
		if(!dfn[y]) {
			dfs(y); 
			low[x]=min(low[x], low[y]); 
			if(low[y]==dfn[x]) {
				cun(x, ++num); 
				while(z.top()!=y) cun(z.top(), num), z.pop(); 
				cun(y, num); z.pop(); 
			}
		}
		else low[x]=min(low[x], dfn[y]); 
	}
}

易错点：

  1. 不用记录父亲，因为普通一条边也可以作为边双的一部分

  2. 由于求的是边双而不是点双，所以判断应为 low[y]==dfn[x] ，表示 yy 最多可以返祖到 xx