DAG 可达性问题小记

Eterna · 2025-09-25 19:02:06 · 算法·理论

DAG 可达性问题

例题 1

给定一张 n 个点 m 条边的有向无环图，分别统计从每个点出发能够到达的点的数量。

记 f_{x,y} 为 x 是否可以走到 y。

对于一条边 (x,y)，如果 f_{y,i}=1，则令 f_{x,i}=1。

建反边，按拓扑序直接转移复杂度 \mathcal{O}(n^2)。

如果将一个 f_{x,1},f_{x,2},\ldots ,f_{x,n-1},f_{x,n} 看作一个二进制数。

那么我们直接令 f_{x}=f_{x}\operatorname{or}f_y 即可。bitset 优化做到 \displaystyle\mathcal{O}(\frac{n^2}{w})。

#include<bits/stdc++.h>
using namespace std;
const int N=30005;
int n,m,vis[N],in[N];
bitset<N> f[N];
vector<int> v[N];
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;++i)f[i][i]=1;
    for(int i=1,x,y;i<=m;v[y].push_back(x),++in[x],++i)cin>>x>>y;
    queue<int> q;
    for(int i=1;i<=n;++i)if(!in[i])q.push(i);
    while(q.size())
    {
        int u=q.front();q.pop();
        for(int i:v[u])
        {
            f[i]|=f[u];
            if(!(--in[i]))q.push(i);
        }
    }
    for(int i=1;i<=n;++i)cout<<f[i].count()<<'\n';
    return 0;
}

例题 2

给出一个 n 个点，m 条边的有向无环图，q 次询问，每次询问给出 x,y,l,r，求是否有一条从 x 到 y 的路径边的编号都在 [l,r] 内。

记一次询问为 (x_i,y_i,l_i,r_i)。

因为对边的编号有 [l_i,r_i] 的限制，所以直接记两点的可达性是不好的。

考虑记 f_{x,i} 表示从 x 出发，只走编号 [l_i,r_i] 能不能到 y_i，再有 g_{x,i}=[l_i\le x\le r_i]。

将 f,g 的第二维开成 bitset。对于一条边 (x,y,\mathrm{id})容易得到转移 f_x=f_x \operatorname{or}(f_y \operatorname{and} g_{\mathrm{id}})。

如果我们知道了 g，那么按反边拓扑序转移容易做到 \displaystyle\mathcal{O}(\frac{mq}{w})。

关于如何求 g，可以先构造 g'，对于每条边 (x,y,\mathrm{id})，我们令 g'_{l_i,\mathrm{id}}=g'_{r_i+1,\mathrm{id}}=1。然后在第一维上做前缀异或即可。

但是这样空间也是 \displaystyle\mathcal{O}(\frac{mq}{w})。

考虑将询问每 B 个分一组，每组单独处理，时间复杂度为 \displaystyle\mathcal{O}(\frac{mq}{w}+\frac{mq}{B})，空间复杂度为 \displaystyle\mathcal{O}(\frac{mB}{w})。

#include<bits/stdc++.h>
#define rd read()
#define gc pa == pb && (pb = (pa = buf) + fread(buf, 1, 100000, stdin), pa == pb) ? EOF : *pa++
using namespace std;
static char buf[100000], * pa(buf), * pb(buf);
inline int read()
{
    register int x=0,s=gc;
    while(!isdigit(s))s=gc;
    while(isdigit(s))x=(x<<1)+(x<<3)+(s^48),s=gc;
    return x;
}
const int N=50005,M=100005,B=1024;
int n,m,q,cnt;
struct query{int x,y,l,r;};
vector<query> d;bitset<B+5> f[N],g[M];
vector<pair<int,int> > v[N];
inline void get()
{
    for(auto [x,y,l,r]:d)++cnt,f[y][cnt]=1,g[l][cnt]=g[l][cnt]^1,g[r+1][cnt]=g[r+1][cnt]^1;
    for(int i=2;i<=m;++i)g[i]^=g[i-1];
    for(int i=n;i>=1;--i)for(auto [j,id]:v[i])f[i]|=f[j]&g[id];
    cnt=0;for(auto [x,y,l,r]:d)cout<<(f[x][++cnt]?"YES\n":"NO\n");
    d.clear();for(int i=1;i<=n;++i)f[i].reset();
    for(int i=1;i<=m;++i)g[i].reset();cnt=0;
}
inline void sol()
{
    n=rd,m=rd,q=rd;for(int i=1;i<=n;++i)v[i].clear();
    for(int i=1,x;i<=m;++i)x=rd,v[x].push_back({rd,i});
    for(int i=1;i<=q;++i){d.push_back({rd,rd,rd,rd});if(i%B==0)get();}get();
}
signed main(){int T=rd;while(T--)sol();return 0;}

例题 3

给定一个 n 个点 m 条边的有向无环图，每个点有点权 (a_i,b_i)。

你需要进行 q 次操作，每次操作交换 a_x 和 a_y 或交换 b_x 和 b_y，或求从 x 出发，能走到的所有 a_y \in [l,r] 的点中的最大 b_y。

发现和上题十分相似。考虑只有询问。

因为对值域的限制只有终点，考虑分别求出 \{i:y\to x_i\} 与 \{y:x \in [l_y,r_y]\} 然后取交集便可以得到一个点可以造成贡献的询问集合 s_j。

如果问题是静态的，则与上题类似。考虑如何动态维护。

在 bitset 上做手脚容易死掉。不妨将每 B 个操作分一组，然后一组一组处理。

对于这 B 次操作中被修改过的，查询时直接暴力判断是否可以走到。对于每次询问，复杂度为 \mathcal{O}(B)。

对于没有被修改过的，将所有 b_i 从大到小排序，求出 s_j 的前缀或，每次或多出来的位置的询问答案就是 b_j，异或一下即可。因为 b 是个排列，所以排序是 \mathcal{O}(n)。

时间复杂度 \displaystyle\mathcal{O}(\frac{n(m+q)}{w}+qB)，空间复杂度 \displaystyle\mathcal{O}(\frac{nB}{w})。

然后好像把 B 开得特别小会非常快，直接用 unsigned long long 连 bitset 都不用。

我代码不知道哪里错了，D 性质过不了，直接特判跑暴力反而过了。

#include<bits/stdc++.h>
#define int long long
#define rd read()
#define gc pa == pb && (pb = (pa = buf) + fread(buf, 1, 100000, stdin), pa == pb) ? EOF : *pa++
#define set(A,x)  A|=1ull<<x
#define flip(A,x) A^=1ull<<x
using namespace std;
static char buf[100000], * pa(buf), * pb(buf);
inline int read()
{
    register unsigned int x=0,s=gc;
    while(!isdigit(s))s=gc;
    while(isdigit(s))x=(x<<1)+(x<<3)+(s^48),s=gc;
    return x;
}
const int N=100005,B=63;
int ID,n,m,q,cnt,rk,a[N],b[N],c[N],ans[B+1];
inline int fir(unsigned int &A){unsigned int k=A&-A;A^=k;return k?__lg(k):0;}
unsigned int g[N],f[N],z,W;bitset<N> is;
struct query{int x,y,l,r;};vector<query> d;
vector<int> p,v[N];
inline void Swap(int x,int y){swap(b[x],b[y]),swap(c[b[x]],c[b[y]]);}
inline void clear()
{
    d.clear(),is=W=0,memset(ans,0,sizeof(ans));
    for(int i=1;i<=n;++i)g[i]=f[i]=0;cnt=0;
}
inline void get()
{
    for(auto [op,x,l,r]:d)if(op==3)set(g[l],cnt),set(g[r+1],cnt),set(f[x],cnt),++cnt;
    else is[x]=is[l]=1; 
    for(int i=1;i<=n;++i)for(int j:v[i])f[j]|=f[i];
    if(ID==17||ID==18)
    {
        cnt=0;
        for(auto [op,x,l,r]:d)if(op==1)swap(a[x],a[l]);
        else if(op==2)Swap(x,l);else{
            for(int j=r;j>=l;--j)
                if((f[c[j]]>>cnt)&1){ans[cnt]=j;break;}
            cout<<ans[cnt++]<<'\n';
        }
        return clear();
    }
    for(int i=2;i<=n;++i)g[i]^=g[i-1];p.clear();
    for(int i=1;i<=n;++i)if(is[i])p.push_back(i);
    for(int i=n,x;i>=1;--i)if(!is[c[i]])
    {
        z=(f[c[i]]&g[a[c[i]]])|W,z^=W,W|=z;
        while(z)x=fir(z),ans[x]=i;
    }cnt=0;
    for(auto [op,x,l,r]:d)if(op==1)swap(a[x],a[l]);
    else if(op==2)Swap(x,l);else{
        for(int j:p)if(a[j]>=l&&a[j]<=r&&((f[j]>>cnt)&1))ans[cnt]=max(ans[cnt],b[j]);
        cout<<ans[cnt++]<<'\n';
    }
    clear();
}
inline void sol()
{
    n=rd,m=rd,q=rd,rk=0;
    for(int i=1,x;i<=m;++i)x=rd,v[x].push_back(rd);
    for(int i=1;i<=n;++i)a[i]=rd;
    for(int i=1;i<=n;++i)c[b[i]=rd]=i;
    for(int i=1,op,x,l,r;i<=q;++i)
    {
        op=rd,x=rd,l=rd;if(op==3)r=rd,++rk;
        d.push_back({op,x,l,r});
        if(d.size()>=1500||rk>=B)get(),rk=0;
    }if(rk)get();for(int i=1;i<=n;++i)v[i].clear();
}
signed main(){ID=rd;int T=rd;while(T--)sol();return 0;}

例题 4

给定一个 n 个点 m 条边的有向图。每条边的颜色是黑色或者白色。

有 q 次操作，每次操作将第 k 条边的颜色进行反转或询问是否能从 u 只经过黑色的边走到 v。

可以发现本题的图是可以有环的，所以大概率是需要缩点的。

与上题类似，我们将操作每 B 个一组，每次处理一组。

对于每组操作中被询问的点和被操作的点和边，把他们拿出来处理，我们分别叫他们关键点和关键边。先使用非关键边对原图缩点，使图变为 DAG。

然后对于每个关键点考虑其可以只经过非关键边到达哪些点，然后对于关键点两两间的联通性建出只有关键点的图。

然后原图上的操作和关键图上的操作是一样的，每次询问用 bitset 优化 BFS 即可。

时间复杂度 \displaystyle\mathcal{O}(\frac{mq+qB^2}{w})。

#include<bits/stdc++.h>
#define rd read()
#define gc pa == pb && (pb = (pa = buf) + fread(buf, 1, 100000, stdin), pa == pb) ? EOF : *pa++
using namespace std;
static char buf[100000], * pa(buf), * pb(buf);
inline int read()
{
    register int x=0,s=gc;
    while(!isdigit(s))s=gc;
    while(isdigit(s))x=(x<<1)+(x<<3)+(s^48),s=gc;
    return x;
}
const int N=50005,M=100005,B=700,S=(B<<1)+2;
int n,m,q,cnt,CNT,gt,q1,q2;
int col[M],X[M],Y[M],sc[N],dfn[N],ID[N];
struct cds{int op,x,y;};
vector<pair<int,int> > v[N],v2[N];
vector<int> G[N],P;vector<cds> d;
bitset<S> f[N],K[S],qr,vs;
bitset<M> is;bitset<N> g,vis;
inline void dfs(int x)
{
    if(vis[x])return;vis[x]=1;
    for(auto [i,t]:v2[x])if(col[i]&&!is[i])dfs(t);
    dfn[++cnt]=x;
}
inline void dfs2(int x,int k)
{
    if(sc[x])return;sc[x]=k;
    for(auto [i,t]:v[x])if(col[i]&&!is[i])dfs2(t,k);
}
inline void Kosaraju()
{
    CNT=cnt=0,vis.reset();for(int i=1;i<=n;++i)sc[i]=0,dfs(i);
    for(int i=n;i>=1;--i)if(!sc[dfn[i]])dfs2(dfn[i],++CNT);
}
inline bool query(int x,int y)
{
    qr.reset(),vs.reset(),qr[gt+1]=qr[x]=1;
    while(1)
    {
        int u=(qr&~vs)._Find_first();
        if(u==y)return 1;if(u>gt)return 0;
        qr|=K[u],vs[u]=1;
    }
}
inline void sol()
{
    is.reset(),g.reset(),P.clear(),gt=0;for(int i=1;i<=n;++i)G[i].clear(),f[i].reset();
    for(auto [op,x,y]:d)if(op==1)is[x]=1,g[X[x]]=g[Y[x]]=1;else g[x]=g[y]=1;
    Kosaraju();for(int i=1;i<=m;++i)if(col[i]&&!is[i])G[sc[X[i]]].push_back(sc[Y[i]]);
    P.push_back(0);for(int i=1;i<=n;++i)if(g[i])P.push_back(i),ID[i]=++gt;
    for(int i=1;i<=gt;++i)K[i].reset();for(int i=1;i<=gt;++i)f[sc[P[i]]][i]=1;
    for(int i=1;i<=CNT;++i)for(int j:G[i])f[i]|=f[j];
    for(int i=1;i<=gt;++i)for(int j=1;j<=gt;++j)if(f[sc[P[i]]][j])K[i][j]=1;
    for(int i=1;i<=m;++i)if(col[i]&&is[i])K[ID[X[i]]][ID[Y[i]]]=1;
    for(auto [op,x,y]:d)if(op==1)col[x]^=1,q1=X[x],q2=Y[x],K[ID[q1]][ID[q2]]=col[x]|f[sc[q1]][ID[q2]];
    else cout<<(query(ID[x],ID[y])?"YES\n":"NO\n");d.clear();
}
signed main()
{   
    n=rd,m=rd,q=rd;
    for(int i=1;i<=m;col[i]=1,++i)X[i]=rd,Y[i]=rd,
        v[X[i]].push_back({i,Y[i]}),v2[Y[i]].push_back({i,X[i]});
    for(int i=1,op,x,y;i<=q;++i)
    {
        op=rd,x=rd;if(op==2)y=rd;
        d.push_back({op,x,y});
        if(d.size()==B)sol();
    }sol();return 0;
}