PTA 那就别担心了(记忆化搜索)
作者:
lpz..
,
2023-04-17 23:26:34
,
所有人可见
,
阅读 185
#include <bits/stdc++.h>
using namespace std;
const int N = 550;
bool st[N];//标记每个点是否被搜过
int e[N][N]; //邻接矩阵存图
int n,m;
int path[N]; //path[x]表示的是从x到y有几条路径
int dfs(int x)
{
st[x] = true;
if (path[x]) return path[x]; //已确定该点通向目标命题的路径总数无需重复记录,减少计算量(记忆化搜索的主要思想)
for (int i = 1;i <= n;i ++)
if (e[x][i]) path[x] += dfs(i);
return path[x];
}
int main()
{
cin >> n >> m;
while (m --)
{
int a,b;
cin >> a >> b;
e[a][b] = 1;
}
int x,y;
cin >> x >> y;
path[y] = 1; //初始化,递归到y就开始回溯,相当于倒推
int cnt = dfs(x);
int f = 1;
for (int i = 1;i <= n;i ++)
if (st[i] && !path[i]) //当某个点搜过了,但到y的路径为0,说明他的父节点的所有路径并不是全都指向y,即不是逻辑自治
{
f = 0;
break;
}
cout << cnt << " ";
if (f) cout << "Yes";
else cout << "No";
return 0;
}