【16届蓝桥杯寒假刷题营】第2期DAY1I

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