4.有向无环的路径数 - 蓝桥云课
问题描述
给定 N 个节点 M 条边的有向无环图，请你求解有多少条 1 到 N 的路径。
由于答案可能很大，你只需要输出答案对 998244353 取模后的结果。
输入格式
第一行包含 2 个正整数 N,M，表示有向无环图的节点数和边数。
之后 M 行，每行给定 2 个正整数 u,v (ueqv 且 1≤u,v≤N)，表示图中存在一条有向边 (u,v)。
输出格式
输出一行，包含一个整数，表示答案，答案对 998244353 取模后的结果。
样例输入
4 4
1 2
2 3
1 3
3 4样例输出
2评测数据规模
对于所有测评数据，1≤N,M≤1e5。
思路：
暴力搜
代码如下：
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
ll n,m,ans,tot;
const ll N = 1e5+10;
const ll mod = 998244353;
ll head[N];
struct Edge{ll next;ll to;
}e[N];
bool vis[N];
void add(ll u,ll v)
{tot++;e[tot].next = head[u];e[tot].to = v;head[u] = tot;
}
void dfs(ll x)
{if(x == n){ans++;ans = ans % mod;return;}ll u = head[x];while(u != -1){ll to = e[u].to;if(!vis[to]){vis[to] = true;dfs(to);vis[to] = false; }u = e[u].next;}
}
int main(void)
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n >> m;for(ll i = 1 ; i <= n ; i++)head[i] = -1;for(ll i = 1 ; i <= m ; i++){ll u,v;cin >> u >> v;add(u,v);}vis[1] = true;dfs(1);cout << ans;return 0;} 
思路：
拓扑排序和dp‘
代码如下：
’
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
ll n,m,ans,tot;
const ll N = 1e5+10;
const ll mod = 998244353;
ll head[N],rd[N],dis[N];
struct Edge{ll next;ll to;
}e[N];
bool vis[N];
void add(ll u,ll v)
{tot++;e[tot].next = head[u];e[tot].to = v;head[u] = tot;
}int main(void)
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);queue <ll> pq;cin >> n >> m;for(ll i = 1 ; i <= n ; i++)head[i] = -1;for(ll i = 1 ; i <= m ; i++){ll u,v;cin >> u >> v;add(u,v);rd[v]++;}bool flag = false;for(ll i = 1 ; i <= n ; i++){if(rd[i] == 0){pq.push(i);if(i == 1){dis[i] = 1;flag = true;}}}while(!pq.empty()){ll pos = pq.front();pq.pop();if(pos == 1 && !flag){dis[pos] = 1;flag = true;}ll u = head[pos];while(u != -1){ll to = e[u].to;rd[to]--;dis[to] = (dis[to] + dis[pos])%mod; if(rd[to] == 0){pq.push(to);}u = e[u].next;} }cout << dis[n];return 0;} 