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;
} 
