7-3 那就别担心了.md

7-3 那就别担心了

题目详情：

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

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

输入格式：

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

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

最后一行给出待检验的两个命题的编号 A B。

输出格式：

在一行中首先输出从 A 到 B 有多少种不同的推理路径，然后输出 Yes 如果推理是“逻辑自洽”的，或 No 如果不是。

题目保证输出数据不超过 109。

输入样例 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

解题思路：

第一种思路肯定是dfs，但是最后一个测试点会超时，所以根据网上一些大神的想法，发现dfs+dp更为合适，即深度优先和记忆化搜索。

题解代码：

#include <bits/stdc++.h>
using namespace std;

int vis[502], path[502], vec[502][502];
int n, m, cnt, a, b;
int DFS(int x) {//深度优先遍历
    //dfs搜索起点到终点路径的条数
    vis[x] = 1;
    if (path[x]) //已经搜索过
        return path[x];
    for (int i = 1; i <= n; i++)//开始搜索
        if (vec[x][i])
            path[x] += DFS(i);
    return path[x];
}
int main() {
    int i;
    cin >> n >> m;
    for (i = 1; i <= m; i++) {
        cin >> a >> b;
        vec[a][b] = 1;
    }
    cin >> a >> b;
    path[b] = 1;
    //初始化b到b的路径条数为1
    //从起点a开始dfs
    cnt = DFS(a);//cnt为满足条件的路径数目
    int flag = 1;//记录是否为逻辑自洽
    for (i = 1; i <= n; i++) {
        if (vis[i] && !path[i]) {
            //表示从该节点i进行搜索，没有一条路径能到达End节点，所以不为逻辑自洽
            flag = 0;
            break;
        }
    }
    cout << cnt << ' ';
    if (flag)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}