跳转至

圆方树

广义圆方树

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
namespace RST
{
    vector<int> G[MAX],T[MAX<<1];
    int dfn[MAX],low[MAX],tot;
    int stk[MAX],top,num;
    void tarjan(int now)
    {
        dfn[now]=low[now]=++tot;
        stk[++top]=now;
        for(auto to:G[now])
            if(!dfn[to])
            {
                tarjan(to),cmin(low[now],low[to]);
                if(low[to]==dfn[now])
                {
                    ++num;
                    do T[num].eb(stk[top]),T[stk[top]].eb(num),--top; while(stk[top+1]!=to);
                    T[num].eb(now),T[now].eb(num);
                }
            }
            else cmin(low[now],dfn[to]);
    }
    inline void build() {for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i);}
}