双极定向 - 方法 1

以 $s$ 为根求出 dfs 树，求出每个点的 $fa(u)$ 和 $low(u)$（最浅能到达的祖先）。

在每个点开一个列表，每次剥掉一个叶子，把该叶子加入 $fa(u)$ 和 $low(u)$ 的列表末尾，表示染黑了 $fa(u)$ 或 $low(u)$ 后就可以染黑 $u$。这样若一个点染黑，则可以将其列表里的点依次染黑，不断递归下去。

假设要求 $s\to t$ 的双极定向。提取 $s\to t$ 的路径，在剥叶子的过程中，不剥掉这条路径上的点。然后将路径从 $s\to t$ 依次染黑，并且递归染黑其列表。

这个做法的本质是：

对于叶子节点，只保留了 $u-fa(u)$ 和 $u-low(u)$ 的边，这样并不改变点连通性。

此时叶子节点度数为 2，进行缩二度点操作：

若 $fa(u)$ 或 $low(u)$ 中有某一个染黑，则立刻染黑 $u$。这样操作，黑与白连通块仍然连通。

https://qoj.ac/submission/521207

int dfn[maxn],low[maxn],fa[maxn],idx,que[maxn],on[maxn];
vi e[maxn],p[maxn];
int cut[maxn];
bool vis[maxn];
void tar(int u,int pa){
    fa[u]=pa;
    dfn[u]=low[u]=++idx,que[idx]=u;
    int ch=0;
    for(auto v:e[u]){
        if(v==pa)continue;
        if(!dfn[v]){
            tar(v,u);
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u] && pa) cut[u]=1;
            ++ch;
        }
        else low[u]=min(low[u],dfn[v]);
    }
    if(!pa && ch>1) cut[u]=1;
}

int q[maxn],len,tim[maxn];
void dfs(int u){
    vis[u]=1;
    q[++len]=u,tim[u]=len;
    for(int v:p[u]) if(!vis[v]) dfs(v);
}
void bipolar(int n,int s,int t){
//    cout<<"bipolar "<<n<<" "<<s<<" "<<t<<"\n";
    For(i,0,n) dfn[i]=low[i]=fa[i]=cut[i]=vis[i]=on[i]=0,p[i].clear(); 
    idx=0,len=0;
    tar(s,0);
    vi path;
    for(int x=t;x;x=fa[x]) on[x]=1,path.pb(x);
    reverse(ALL(path));
    Rep(i,n,1){
        int u=que[i];
        if(!on[u]) p[fa[u]].pb(u),p[que[low[u]]].pb(u);
    }
    for(int x:path) dfs(x);
}

双极定向 - 方法 2

这里考虑将所有边定向。

先以 $s$ 为根求出 dfs 树，然后将 $s\to t$ 的路径定向成“向下”。

我们先把 $t$ 推进队列里，并把它标记为“向下”（向队列中加入 $(t,\downarrow)$）。

从队列里取出一个点 $t$，然后不断向上爬祖先，把 $t$ 到某个祖先都标记成相应的方向，直到碰到一个标记过的祖先边结束。

假设我们当前定向了 $(x,y)$ 这条边。这时碰到一条返祖边 $(x,u)$ 且 $u$ 在 $y$ 的子树中（重要细节：不要考虑 $u$ 不在 $y$ 子树中的返祖边）。此时需要给这条返祖边 $(x,u)$ 定向成 $(x,y)$ 相同的方向，然后将 $u$ 向上的一段树边路径定向成 $(x,y)$ 相反的方向。

把 $u$ 和这个对应方向推进队列里（比如下图就是加入 $(u,\uparrow)$），不断 bfs 即可。

我们发现这个过程相当于加入了一个“耳”。

具体实现的话，假设返祖边 $(x,u)$ 对应路径 $x\to y\to \dots \to u$，将这条返祖边加入 $y$ 的列表。定向树边 $(x,y)$ 时遍历一下 $y$ 的列表即可。

https://codeforces.com/contest/730/submission/257809370

int n,m,s,t;
vector<pii>e[maxn],et[maxn];
int fa[maxn],fe[maxn],dep[maxn];
int eu[maxn],ev[maxn];
int to[maxn];

void dfs(int u){
//    cout<<"dfs "<<u<<" "<<fa[u]<<" "<<dep[fa[u]]+1<<"\n";
    dep[u]=dep[fa[u]]+1;
    for(auto [v,i]:e[u]){
        if(i==fe[u])continue;
        if(!dep[v]){
            fa[v]=u,fe[v]=i;
            to[u]=v;
            dfs(v);
        }
        else if(dep[v]<dep[u]) et[to[v]].pb(mkp(u,i));
    }
}

pii q[maxn];
int hd,tl;
bool vis[maxn];
bool ve[maxn];

void go(int i,int d){
    ve[i]=1;
    if(dep[eu[i]]>dep[ev[i]]) swap(eu[i],ev[i]);
    if(d) swap(eu[i],ev[i]);
}
void decomp(){
    hd=1,tl=0;
    q[++tl]=mkp(t,0); // 0:dw 1:up
    while(hd<=tl){
        auto [u,d]=q[hd++];
        if(vis[u])continue;
        while(!vis[u]){
            vis[u]=1;
            if(u==s)break;
            go(fe[u],d);
        //    if(!vis[u]) q[++tl]=mkp(u,d);
            for(auto [v,j]:et[u]){
                go(j,d);
                if(!vis[v]) q[++tl]=mkp(v,!d);
            }
            u=fa[u];
        }
    }
}