题解：AT_ndpc2026_b DAG

manboo · 2026-05-07 07:25:13 · 题解

题意概述：

给你 n\left(2\le n\le2\times10^5\right) 个点，m\left(0\le m\le\min\left(\frac{n\times\left(n-1\right)}{2},2\times10^5\right)\right) 条边的有向无环简单图，求 1 到 n 的路径数量模 998244353。

不难发现这道题是 ndpc 的题，于是考虑 dp。

设 f_x 表示从 1 到 x 的路径数量，当然初值即为 f_1=1，那么对于每一条有向边 x\rightarrow y，所有 1 到 x 的路径，都可以到 y，因此会让 f_y\leftarrow f_y+f_x。

为了让 dp 满足无后效性，我们进行如上转移时，必须保证 f_x 已经正确求出，且当 f_y 正确求出后才可以更新其它点，因此 dp 的顺序应按照拓扑序。

具体来说，初始把所有入度为 0 的点放入队列，一直取队列顶 x，枚举以 x 为出发点的边所到达的点 y，令 f_y 的值加上 f_x，并让 y 的入度减 1，当 y 的入度为 0 时，把 y 放入队列。

最终答案即为 f_n。

问：为什么一定能得到 f_n 呢？

答：因为这是有向无环图，所以它一定有完整的拓扑序，也就一定可以得到 f_n 了。

问：为什么初始要把所有入度为 0 的点放入队列？只放 1 不行吗？

答：不行。虽然只有 f_1 有初值为 1，其它入度为 0 的点的 f 初值都是 0，并不会对其它点的 f 值造成影响，但是会对其他点的入度造成影响，为了得到正确、完整的拓扑序，必须把所有入度为 0 的点放入队列，并且这样是不会影响答案的。

下面是代码时间！

const int N=200001,mod=998244353;
int n,m,du[N],f[N];
//du[i]为i的入度，f[i]为i的f值 
vector<int> son[N];
//son[x]存储以x为出发点的边所到达的点y 
inline void topsort()
{
    queue<int> q;
    for(int i=1;i<=n;i++) if(!du[i]) q.push(i);
    while(q.size())
    {
        int x=q.front();
        q.pop();
        for(auto y:son[x])
        {
            (f[y]+=f[x])%=mod;
            if(!--du[y]) q.push(y);
        }
    }
}
inline void solve()
{
    n=read(),m=read();
    for(int i=1;i<=n;i++) du[i]=f[i]=0,son[i].clear();  //多测要清空 
    for(int i=1,x=0,y=0;i<=m;i++)
    {
        x=read(),y=read();
        son[x].push_back(y),du[y]++;
    }
    f[1]=1,topsort();
    print(f[n]),putchar('\n');
}
int main()
{
    for(int T=read();T;T--) solve();
    return 0;
}