虚幻大学 xuhss 361℃ 0评论

? 优质资源分享 ?

学习路线指引(点击解锁) 知识定位 人群定位
? Python实战微信订餐小程序 ? 进阶级 本课程是python flask+微信小程序的完美结合,从项目搭建到腾讯云部署上线,打造一个全栈订餐系统。
?Python量化交易实战? 入门级 手把手带你打造一个易扩展、更安全、效率更高的量化交易系统

支配树:在 O(nlogn)O(n\log n) 时间内求出一张有向图中能切断一个点到起点的所有路径的点

具体地,先定义一个起点 SS(要求它能到达所有点),对于图中一个点 uu,存在一些点 vv,使得删去某个 vv 后 SS 无法走到 uu,这些点 vv 所组成的集合就是支配树上 uu 到根的路径。特别地,uu 的父亲就是离它最近的支配点。

一个很重要的性质:对于任意点 uu,如果 xx 支配 uu 且 yy 支配 uu,则 xx 与 yy 之间存在支配关系。
证明显然。由此不难推出支配关系形成一棵树。

求支配树的方法:

1. DAG 上求支配树

按照拓扑序枚举所有点,对于一个点 uu,所有能到达它的点的支配树已经求出, 于是我们枚举 uu 的入点 vv,找出它们在已求出的支配树上的 LCA,即为 uu 的支配点(证明感性理解),然后将 uu 加入支配树。

注意我们需要“动态”求这个 LCA,这问题不大,我们只需要每找到一个 uu 的父亲时就立即更新它的倍增数组 fa[u][i] 即可。时间复杂度就 O(nlogn)O(n\log n)。

2. 一般图上求支配树

我们发现在 DAG 上很好做,考虑将一般图鼓捣成一个 DAG 且支配关系不变。

用著名的 Tarjan 思想,我们先搜出一棵 dfs 树再说。立即发现一个点 uu 的支配点一定在它的dfs树的祖先中。

接下来,引入一个大家初学 Tarjan 就熟知的定理:对于有向图的 dfs 树而言,只存在前向边与反向边,不存在横叉边。
即只有祖先向孙子连边或孙子向祖先连边。

同样 DAG 部分,这次我们按dfs序逆序对每个点 uu 考虑它的所有入点 vv,维护一个“半支配点”semiusemi_u。
分两种情况:

  1. vv 为 uu 的祖先。
    此时 vv 能一步走到 uu,所以从 vv 到 uu 的路径上所有其它点都不可能成为 uu 的支配点(否则压根切不断),所以 uu 的真实支配点应该在 vv 上方,故用 vv 更新 uu 的半支配点。(这里的更新指取 dfs 序最小的作为答案)
  2. vv 为 uu 的子孙。
    此时我们考虑 uu 到 vv 的路径上所有点 ww 以及它们的半支配点 semiwsemi_w,发现如果我们割的点在任意一个 semiwsemi_w 下方,那么从根就可以走路径 S→semiw→w→v→uS\rightarrow semi_w\rightarrow w\rightarrow v\rightarrow u 到达 uu,矛盾。因此用所有 ww 的半支配点 semiwsemi_w 更新 uu 的半支配点 semiusemi_u。
    画个图理解一下:
    2560578 20221007222917091 341503606 -

更新完毕后,我们就得到了每个点 uu 的“半支配点”。“半支配点”的本质意义在于,uu 的真实支配点一定在它的半支配点到根的路径上。因此只保留 dfs 树上的边以及新加入的 semiu→usemi_u\rightarrow u 的边,整张图的支配关系不变。

于是我们只保留原 dfs 树中的边,将其它边统统删掉,然后对于每个 uu 加入边 semiu→usemi_u\rightarrow u,在这个新的只有 2(n−1)2(n-1) 条边的 DAG 上跑做法 1 即可。

现在只剩下怎么快速对一个点 vv 找出 uu 到 vv 的路径上所有 ww 的 semiwsemi_w 的 dfs 序最小值的问题了。

考虑维护每个点 vv 已访问的祖先中 semisemi 的最小值 mnvmn_v,查询时恰好就是查询 vv 的 mnvmn_v(因为 vv 的祖先中第一个未访问的点就是 uu)。用并查集维护,每次访问完一个节点 uu 就被其父亲 faufa_u 合并即可。时间复杂度 O(nα(n))O(n\alpha(n)) 或 O(nlogn)O(n\log n)(我们都懒得写按秩合并对吧)。

总时间复杂度 O(nlogn)O(n\log n)。

上一个封装好的代码:(注意代码中 mnumn_u 直接写成了 semi[u],所以必须在访问完一个 uu 之后立即将其加入新图中)

洛谷 P5180 【模板】支配树

#include 
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rev(i,a,b) for(int i=a;i>=b;i--)
#define Fin(file) freopen(file,"r",stdin)
#define Fout(file) freopen(file,"w",stdout)
using namespace std;
const int N=2e5+5; typedef long long ll;
class DominatorTree{
    int n,dfn[N],raw[N],dfscnt,semi[N],fa[N],pa[N],ffa[N][18],dep[N],in[N];
    vector<int> to[N],from[N],cp[N],cv[N];
    void dfs(int u){
        raw[dfn[u]=++dfscnt]=u; for(int v:to[u]) if(!dfn[v]) { cp[u].push\_back(v); pa[v]=u; dfs(v); }
    }
    int getfa(int x){
        if(x!=fa[x]) { int t=getfa(fa[x]); semi[x]=min(semi[x],semi[fa[x]]); fa[x]=t; } return fa[x];
    }
    int lca(int x,int y){
        if(dep[x]swap(x,y);
 Rev(i,17,0) if(dep[ffa[x][i]]>=dep[y]) x=ffa[x][i];
 if(x==y) return x;
 Rev(i,17,0) if(ffa[x][i]!=ffa[y][i]) { x=ffa[x][i]; y=ffa[y][i]; }
 return ffa[x][0];
 }
public:
 void init(int \_n) { n=\_n; }
 void add\_edge(int x,int y) { to[x].push\_back(y); from[y].push\_back(x); }
 void solve(int* ans){
 dfs(1); assert(dfscnt==n);
 For(i,1,n) { fa[i]=i; semi[i]=dfn[i]; }
 Rev(i,n,2){
 int u=raw[i]; for(int w:from[u]) { getfa(w); semi[u]=min(semi[u],semi[w]); }
 fa[u]=pa[u]; cp[raw[semi[u]]].push\_back(u); // Must do it right now!
 }
 For(u,1,n) for(int v:cp[u]) { cv[v].push\_back(u); in[v]++; }
 static int q[N],h,t; h=t=0; q[t++]=1;
 while(hint u=q[h++]; ans[u]=0;
 for(int v:cv[u]) if(ans[u]==0) ans[u]=v; else ans[u]=lca(ans[u],v);
 dep[u]=dep[ffa[u][0]=ans[u]]+1; For(i,1,17) ffa[u][i]=ffa[ffa[u][i-1]][i-1];
 for(int v:cp[u]) if((--in[v])==0) q[t++]=v;
 }
 }
}T;
int n,m,ans[N],siz[N]; vector<int> son[N];
void dfs(int u) { siz[u]=1; for(int v:son[u]) { dfs(v); siz[u]+=siz[v]; } }
signed main(){
 ios::sync\_with\_stdio(false); cin.tie(0); cout.tie(0);
 cin>>n>>m; T.init(n); For(i,1,m) { int x,y; cin>>x>>y; T.add\_edge(x,y); } T.solve(ans);
 // For(i,1,n) cerr<
 For(i,2,n) son[ans[i]].push\_back(i);
 dfs(1); For(i,1,n) cout<' '; cout<"Time = "<<clock()<<" ms\n";
 return 0;
}

// START TYPING IF YOU DON'T KNOW WHAT TO DO

转载请注明:xuhss »

喜欢 (58)

您必须 登录 才能发表评论!