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

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

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

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

圆方树：

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
3
4
5
6
7
8
9
10
11
12
13
14
15
16

易错点：

1. 不用记录父亲，因为普通一条边也可以作为边双的一部分
2. 由于求的是边双而不是点双，所以判断应为 low[y]==dfn[x]，表示 $y$ 最多可以返祖到 $x$