园方树

· · 个人记录

园方树

一种可以把图转换成树的神奇东东

用途

  1. 把图转换成树
  2. 求一条路径上的割点数量

    过程

    把原图上的点称做圆点

把每一个点双内部的边删除，每个点双新建一个点，叫方点，连向点双内所有圆点

两个圆点之间的割点，就是圆方树上，两个点路径经过的所有圆点

完了？啊对，就完了

代码

建图

e[i*2].nxt=heade[u];e[i*2].to=v;heade[u]=i*2;
e[i*2+1].nxt=heade[v];e[i*2+1].to=u;heade[v]=i*2+1;
//heade是原图,headt是园方树

link函数

void link(ll u,ll v)
{
    t[++cnt].nxt=headt[u];t[cnt].to=v;headt[u]=cnt;
    t[++cnt].nxt=headt[v];t[cnt].to=u;headt[v]=cnt;
}

tarjan

dfn[u]=++tot;
low[u]=dfn[u];
st.push(u);
for(int i=heade[u];i;i=e[i].nxt)
{
    ll v=e[i].to;
    if((i^1)==f)continue;
    if(!dfn[v])
    {
        tarjan(v,i);
        low[u]=min(low[u],low[v]);
        if(low[v]>=dfn[u])
        {
            SCC++;
            link(SCC,u);
            while(st.top()!=v)
            { 
                link(SCC,st.top());st.pop();
            }
            link(SCC,v);st.pop();
        }
    }
    else
    {
        low[u]=min(low[u],dfn[v]);
    }
}
//没有特判单个节点的情况

重点是刷题

题目

p4606战略游戏