引用

刚开始想到了怎么做，但是想不明白该怎么判断是否有些点不能达到终点，在群里问了一些大佬还是不能理解，看了大佬的题解之后，再结合群里的大佬所说的，瞬间就理解了，嘤嘤嘤

巴扎嘿呀 L3-1 那就别担心了（记忆化搜索）

题目描述

下图转自“英式没品笑话百科”的新浪微博 —— 所以无论有没有遇到难题，其实都不用担心。
2020天梯赛总决赛L3-1

博主将这种逻辑推演称为“逻辑自洽”，即从某个命题出发的所有推理路径都会将结论引导到同一个最终命题（开玩笑的，千万别以为这是真正的逻辑自洽的定义……）。现给定一个更为复杂的逻辑推理图，本题就请你检查从一个给定命题到另一个命题的推理是否是“逻辑自洽”的，以及存在多少种不同的推理路径。例如上图，从“你遇到难题了吗？”到“那就别担心了”就是一种“逻辑自洽”的推理，一共有 3 条不同的推理路径。

样例

输入格式

输入首先在一行中给出两个正整数 N（1<N≤500）N（1<N≤500） 和 M，分别为命题个数和推理个数。这里我们假设命题从 1 到 N 编号。

接下来 M 行，每行给出一对命题之间的推理关系，即两个命题的编号 S1 S2，表示可以从 S1 推出 S2。题目保证任意两命题之间只存在最多一种推理关系，且任一命题不能循环自证（即从该命题出发推出该命题自己）。
最后一行给出待检验的两个命题的编号 A B。

输出格式

在一行中首先输出从 A 到 B 有多少种不同的推理路径，然后输出 Yes 如果推理是“逻辑自洽”的，或 No 如果不是。
题目保证输出数据不超过 10910^9

输入样例 1：

7 8
7 6
7 4
6 5
4 1
5 2
5 3
2 1
3 1
7 1

输出样例 1：

3 Yes

输入样例 2：

7 8
7 6
7 4
6 5
4 1
5 2
5 3
6 1
3 1
7 1

输出样例 2：

3 No

算法

(记忆化搜索) O(n2)O(n^2)

个人感觉这是一个很简单的图论题。由题目的意思我们可以知道，只需要存下所有命题能推导什么命题就行了。相信聪明的你已经想到了，那就是邻接表。至于邻接表呢就是一个用于存储图的结构，相信邻接矩阵大家都熟悉吧，就是用一个二维矩阵存储某个点是否能到另一个点的信息比如第一行第二列的数不为0，就表示1这个点能到2这个点，如果带权值那么数组的值就是权值。但是邻接矩阵一般不用来存无向图，因为你不能存两条边的信息，而且也浪费空间。所以对于图的存储我们可以用邻接表。其实邻接表就是一条单链表上的每一个节点都是一条单链表，上面存储了这个头结点能到那个点上，存储顺序无关紧要。

这道题其实是有向无环图的遍历，我们先把每个点能到的点连一条边（如果是无环图就反向连一条就行），即在头结点上用头插法把节点插入就行了。因为按照题目的意思我们不仅要找到起点延申出来的点有几条能到终点，还有判断是否都能到终点。所以对于这种遍历我们可以采用dfs，一条路走到底，但是因为数据范围比较大，能多点可能会交错，如果只是单纯的遍历是不能在规定时间内跑完的，所以我们应该存下已经遍历的点到达终点的路径数，这样在第二次遍历这个点的时候就不用再次遍历了，也就是记忆化搜索。

时间复杂度 O(n)O(n)

所有点都只搜一次，嗯，应该是这样的

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1000;

//h用于存储头结点，初始化为-1  e为数据域，存储能到的点  ne为指针域 idx表示当前用到的是第几个节点
int h[N] , e[N * N] , ne[N * N] , idx;
int num[N];

//将两点之间连一条边，头插法
void add(int a , int b)
{
    e[idx] = b , ne[idx] = h[a] , h[a] = idx ++;
}

int n , m , x , y , flag;

int dfs(int u)
{
    int res = 0;
    //如果这个点搜过了就直接返回以它为起点的路径数
    if(num[u] != -1) return num[u];
    //如果搜到了终点，那么这个点的值为1，即以它为起点的路径只有一条
    if(u == y) return num[u] = 1;
    //如果这个为NULL,那么表示以这个点为起点的路径为0，并且它不能到达终点
    if(h[u] == -1)
    {
        flag = 1;
        return num[u] = 0;
    }
    
    //遍历每条链表上的点
    for(int i = h[u]; i != -1; i = ne[i])
    {
        //因为是有向无环图，所以不需要记录这个点是不是被遍历过
        int j = e[i];
        res += dfs(j);
    }
    //遍历完返回结果
    return num[u] = res;
}

int main()
{   
    
    memset(h, -1, sizeof h);
    memset(num , -1 , sizeof num);
    
    cin >> n >> m;
    
    for(int i = 0; i < m; i ++)
    {
        int a , b;
        cin >> a >> b;
        add(a, b);
    }
    
    cin >> x >> y;
    
    int res = dfs(x);
    
    cout << res << ' ';
    //如果为真代表有至少一个点不能到达终点
    if(flag || !res) cout << "No";
    else cout << "Yes";
  
    return 0;
}