一种 DAG 上可达性判定问题的解决方案

zifanwang · 2025-12-07 16:58:24 · 算法·理论

本文发表于 https://www.cnblogs.com/zifanoi/p/19318662（洛谷上不一定保持同步）。

1. 问题简述

给定一个有向无环图 G=(V,E)，记 n=|V|，m=|E|。有 q 次查询，每次给定两个点 a 和 b，判断是否存在一条以 a 为起点，b 为终点的简单路径。

其中 n,m 同阶，保证 \forall (u,v)\in E,u<v。

（容易用 bitset 做到 \mathcal O(\frac{nm}w+q)）

1.1 任意图

去除 DAG 的限制，即给定的图为任意有向图。此时进行一次缩点，即可转化为 DAG 问题，本质上是一样的。

1.2 树

限制给定的图是树的形态，则可以构造 dfn 序，容易做到 \mathcal O(n+q\log n)。

2. 定义

2.1 有向无环图（DAG）

设 G=(V,E) 是一个有向图，其中：

我们称 G 是一个有向无环图（DAG），若 不存在 长度大于等于 1 的顶点序列 v_0,v_1,\dots,v_k 使得 \forall i\in [0,k-1]\cap\mathbb{Z}, (v_i,v_{i+1})\in E 且 v_0 = v_k。

即不存在从某个点出发又回到自身的有向路径。

2.2 搜索树（有向根树 / arborescence）

称 S=(V,E_S,r) 为 G 的一个搜索树（有向根树），当且仅当：

• 在有向图 (V,E_S) 中，r\in V 为根，并且对于任意顶点 v\in V\setminus\{r\}，存在且唯一一条由 r 出发、沿着 E_S 的有向路径到达 v。
  （等价地，每个 v\ne r 在 E_S 中有且只有一条入边，且 (V,E_S) 无有向环。）

我们有时把这样的结构也称为以 r 为根的有向生成树（arborescence）。

2.3 树剖（暂时没有用到）

先将有向树转为无向以便树剖定义：

树剖通常定义在无向图上。为此对 S 定义其对应的无向化（忽略方向）：

令 T=(I,F) 为一棵树，包函数为 \chi: I\to 2^V。则称 (T,\chi) 为图 \operatorname{und}(S) 的一个树剖当且仅当下面三条成立：

1. 覆盖：\bigcup_{i\in I}\chi(i)=V。

2. 边被包含：对任意无向边 \{u,v\}\in E_S^{\mathrm{u}}，存在 i\in I 使得 \{u,v\}\subseteq\chi(i)。

3. 连通性/子树性质：对任意顶点 v\in V，集合 \{\,i\in I\mid v\in\chi(i)\,\} 在树 T 中构成一个连通子树。

树剖的宽度定义为

2.4 DFS 序

设给定搜索树（有向根树）

其中 r 为根，且对任意 v\ne r 在 E_S 中有且只有一条入边（即每个顶点有唯一父亲）。

记 n=|V|。

定义一个排列（序列）

满足 \pi 是双射。将 \pi 称为一个 DFS 序，其中 \pi(k) 表示第 k 个被首次访问的顶点。

定义顶点的 dfn 值为

于是

3. 解决方案

本文探讨一种类似树剖的做法，构造某种 DFS 序将问题简化。

3.1 整体思路

构造 G 的一个搜索树 S 以及 S 的一个 DFS 序，并对 DAG 上的每个点预处理出该点可以到达的所有点的 dfn 值构成的连续区间的集合。

查询时通过二分判断是否存在一个区间包含 \mathrm{dfn}(b)，做到 \mathcal O(\log \sigma(a))，其中 \sigma(a) 为连续段数。

3.2 具体做法

设有向无环图（DAG）

并令 x\in V。记顶点的出度为

定义从 x 出发的路径集（允许长度 0 的空路径）：

对路径 p=(v_0,\dots,v_k) 定义其终点 \mathrm{end}(p):=v_k，则按路径计数的出度之和记为：

在有限的 DAG 上 \mathcal P_x 有限，因此上式是有限和。

对 G 进行一次深度优先搜索，对于每个点 x 连到的点 \{y\mid(x,y)\in E\}，按 S_{\mathrm{mult}}(y) 从大到小依次尝试访问，得到一个 DFS 序。然后暴力预处理每个点可以到达的所有点的 dfn 值构成的连续区间的集合。

查询直接二分然后判一下。

记 d=\max_{a\in V}\{\sigma(a)\}，则时间复杂度为 \mathcal O(\sum_{(u,v)\in E}\sigma(v)\log d+q\log d)。

3.3 参考代码

#include<bits/stdc++.h>
#define ll long long
#define mxn 200003
#define md 1000000007
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define rept(i,a,b) for(int i=(a);i<(b);++i)
#define drep(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
inline int read(){
    int x=0;bool flag=true;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')flag=false;ch=getchar();}
    while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return flag?x:-x;
}
struct node{
    int l,r;
}st[mxn*200];
int n,m,q,tot,c[mxn],rt[mxn],dfn[mxn],a[205][205];
vector<int>g[mxn],e[mxn];
vector<node>s[mxn];
bool v[mxn];
ll sz[mxn];
void dfs(int x){
    dfn[x]=++tot,v[x]=1;
    sort(g[x].begin(),g[x].end(),[](int x,int y){
        return sz[x]>sz[y];
    });
    for(int i:g[x])if(!v[i]){
        e[x].pb(i);
        dfs(i);
    }
    rt[x]=tot;
}
inline void add(int x,int y){
    g[x].pb(y),c[y]++;
}
void build(){
    n=read(),m=read();
    for(int i=0,x,y;i<m;++i){
        x=read(),y=read();
        add(x,y);
    }
}
signed main(){
    build();
    rep(i,1,n){
        if(!c[i])g[0].pb(i);
        sz[i]=g[i].size();
    }
    drep(i,n,1){
        for(int j:g[i])sz[i]+=sz[j];
    }
    tot=-1;
    dfs(0);
    tot=0;
    ll mx=0,sum=0;
    drep(i,n,1){
        st[tot=1]={dfn[i],rt[i]};
        for(int j:g[i])for(node k:s[j])st[++tot]=k;
        sort(st+1,st+tot+1,[](node x,node y){
            return x.l==y.l?x.r>y.r:x.l<y.l;
        });
        rep(j,1,tot){
            if(s[i].empty())s[i].pb(st[j]);
            else if(st[j].l>s[i][s[i].size()-1].r+1)s[i].pb(st[j]);
            else s[i][s[i].size()-1].r=max(s[i][s[i].size()-1].r,st[j].r);
        }
        mx=max(mx,(ll)s[i].size());
        sum+=s[i].size();
    }
    cerr<<mx<<" "<<(double)sum/n<<'\n';
    q=read();
    int x,y;
    while(q--){
        x=read(),y=dfn[read()];
        int l=0,r=s[x].size()-1;
        while(l<r){
            int mid=(l+r)>>1;
            if(s[x][mid].l<=y)r=mid;
            else l=mid+1;
        }
        puts(s[x][l].r>=y&&s[x][l].l<=y?"Yes":"No");
    }
    return 0;
}

4. 对于各类图的复杂度分析

咕咕咕

4.1 一种随机图：

考虑通过以下方式建图：

void build(){
    mt19937 mt((unsigned ll)new char);
    n=1e4,m=2e5;
    rep(i,1,m){
        int x=mt()%n+1,y=mt()%n+1;
        while(x==y)x=mt()%n+1,y=mt()%n+1;
        if(x>y)swap(x,y);
        add(x,y);
    }
}

输出数据：203 115.135。

取 m=1e5：353 175.38。

取 n=1e5,m=2e5：71 6.5275。

运行时间较短。

4.2 在随机树上随机撒边：

考虑通过以下方式建图：

void build(){
    mt19937 mt((unsigned ll)new char);
    n=1e5,m=2e5;
    rept(i,1,n){
        add(mt()%i+1,i+1);
    }
    rep(i,1,m-n+1){
        int x=mt()%n+1,y=mt()%n+1;
        while(x==y)x=mt()%n+1,y=mt()%n+1;
        if(x>y)swap(x,y);
        add(x,y);
    }
}

输出数据：11342 20.3504。

运行时间较短。

4.3 在菊花图/链上随机撒边：

考虑通过以下两种方式建图：

void build(){
    mt19937 mt((unsigned ll)new char);
    n=1e5,m=2e5;
    rept(i,1,n){
        add(1,i+1);
    }
    rep(i,1,m-n+1){
        int x=mt()%n+1,y=mt()%n+1;
        while(x==y)x=mt()%n+1,y=mt()%n+1;
        if(x>y)swap(x,y);
        add(x,y);
    }
}

void build(){
    mt19937 mt((unsigned ll)new char);
    n=1e5,m=2e5;
    rept(i,1,n){
        add(i,i+1);
    }
    rep(i,1,m-n+1){
        int x=mt()%n+1,y=mt()%n+1;
        while(x==y)x=mt()%n+1,y=mt()%n+1;
        if(x>y)swap(x,y);
        add(x,y);
    }
}

输出数据分别为：9 1.74156，11 5.24551，运行时间较短。

5. Hack

忘了，咕咕咕。

6. 拓展

该算法将可达点转化为若干区间，容易处理一些更复杂的问题。

6.1 可达点权值之和

处理出可达点区间，容易通过处理前缀和快速查询。

用一些类似根号分治的东西可以将权值动态化。