L3-025 那就别担心了 (30 分)-PAT 团体程序设计天梯赛 GPLT

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

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

分析：Edge中储存第i个命题可以推出的命题编号，A、B表示起始路径和终点路径，laneNum[i]储存从第i个命题到第B个命题有多少种不同的推理路径，laneNum[B]的初始值为1。consistency表示推理是否逻辑自洽。通过记忆化dfs从A点开始更新laneNum的值，index表示当前所在的命题编号，如果laneNum[index]为0则表示已经向后搜索过，直接返回其数值即可～将laneNum[index]加上它所有可以到达的后续节点Next的laneNum值，如若某点的laneNum值为0，则表示从A出发到这一命题，不能继续向下推理到命题B，则标记consistency为1～

#include <bits/stdc++.h>
using namespace std;
int N, M, S1, S2, A, B, consistency, laneNum[502];
vector<int> Edge[502];
int dfs(int index) {
    if (laneNum[index] != 0) return laneNum[index];
    for (int Next : Edge[index]) {
        if (laneNum[Next] == 0) dfs(Next);
        laneNum[index] += laneNum[Next];
    }
    if (laneNum[index] == 0) consistency = 1;
    return laneNum[index];
}
int main() {
    cin >> N >> M;
    for (int i = 0; i < M; ++i) {
        cin >> S1 >> S2;
        Edge[S1].push_back(S2);
    }
    cin >> A >> B;
    laneNum[B] = 1;
    dfs(A);
    cout << laneNum[A] << ' ' << (consistency ? "No" : "Yes");
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

int N, M, S1, S2, A, B, consistency, laneNum[502];

vector<int> Edge[502];

int dfs(int index) {

if (laneNum[index] != 0) return laneNum[index];

for (int Next : Edge[index]) {

if (laneNum[Next] == 0) dfs(Next);

laneNum[index] += laneNum[Next];

}

if (laneNum[index] == 0) consistency = 1;

return laneNum[index];

}

int main() {

cin >> N >> M;

for (int i = 0; i < M; ++i) {

cin >> S1 >> S2;

Edge[S1].push_back(S2);

}

cin >> A >> B;

laneNum[B] = 1;

dfs(A);

cout << laneNum[A] << ' ' << (consistency ? "No" : "Yes");

return 0;

}

❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版