圆方树

_Luminous · 2025-02-22 14:56:56 · 算法·理论

圆方树是什么？

是一种将图变为树的方法，可以把一般图上的某些问题转化到树上考虑，容易通过很多常见数据结构维护。

定义

在圆方树中，原来的每个点对应一个 圆点，每一个点双对应一个 方点。

构造

只考虑联通图（不联通则拆分成每个联通子图考虑）。

因为圆方树基于点双，点双基于割点，所以只需要用类似求割点的方法即可（即 Tarjan）。

注：圆方树的点数小于 2n，数组大小要开两倍。

从 n+1 开始，对于找到的每个点双构建一个方点，同时点双内的点与新建的方点连边即可。

Tarjan 建树

vector<int> T[N*2];
int idx,dfn[N],low[N];
int top,stk[N];
int square=n;
void Tarjan(int u){
    low[u]=dfn[u]=++idx;
    stk[++top]=u;
    for(int v:G[u])
        if(!dfn[v]){
            Tarjan(v);
            low[u]=min(low[u],low[v]);
            if(low[v]==dfn[u]){
                square++;
                int x=0;
                do{
                    x=stk[top];
                    T[square].push_back(x);
                    T[x].push_back(square);
                    top--;
                }while(x!=v);
                T[square].push_back(u);
                T[u].push_back(square);
            }
        }
        else low[u]=min(low[u],dfn[v]);
}