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