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