圆方树

前置知识：

点双连通分量
tarjan 求点双

对于一个无向图，在维护某些信息时可以利用圆方树的方法把原图转为一棵树来处理

我们称在原图上的点是圆点

对于每个点双联通分量，新建一个连向点双内所有点的新点，称其为方点

点双内的所有点除了向方点连边以外不向点双内其他点连边，换句话说一个点双内，以方点为中心形成了一个菊花图的形状

来自WC的PPT~~(和小粉兔的博客)~~

1126418-20190711015718548-2063534813.png (1080×410) (cnblogs.com)

点双的数量 $<n$，所以圆方树的点数 $<2n$

显然如果原图有 $k$ 个联通块，则原图会形成一个 $k$ 棵树组成的森林

Tarjan 构造圆方树

利用 Tarjan 可以在求点双的同时顺便把圆方树建出来，在统计同一个点双里面的点的时候加一个向方点连边的过程即可

为了风格统一这里没有使用通常建圆方树时点入栈的方法，而是平时tarjan的边入栈

void dfs(int u, int fa) {
	low[u] = rnk[u] = ++dfc;
	int child = 0;
	for(int i : G[u]) {
		auto e = E[i];
		int v = e.v;
		if(!rnk[v]) {
			stk.push(e);
			dfs(v, u);
			low[u] = min(low[v], low[u]);
			child++;

			if(low[v] >= rnk[u]) {
				is_cut[u] = true;
				bcccnt++;

				while(1) {
					auto x = stk.top();
					stk.pop();
                    //建圆方树
					if(bccnu[x.u] != bcccnt)
						add2(x.u, n + bcccnt), bccnu[x.u] = bcccnt;
					if(bccnu[x.v] != bcccnt)
						add2(x.v, n + bcccnt), bccnu[x.v] = bcccnt;
					if(x == e)
						break;
				}
			}
		} else if(rnk[v] < rnk[u] && v != fa) {
			stk.push(e);
			low[u] = min(low[u], rnk[v]);
		}
	}
	if(fa == 0 && child == 1)
		is_cut[u] = 0;
}
inline void tarjan() {
	for(int u = 1; u <= n; u++)
		if(!rnk[u])
			dfs(u, 0);
}