简答题
偏难
#7503
那就别担心了 下图转自“英式没品笑话百科”的新浪微博 —— 所以无论有没有遇到难题,其实都不用担心。 博主将这种逻辑推演称为“逻辑自洽”,即从某个命题出发的所有…
那就别担心了
下图转自“英式没品笑话百科”的新浪微博 —— 所以无论有没有遇到难题,其实都不用担心。

博主将这种逻辑推演称为“逻辑自洽”,即从某个命题出发的所有推理路径都会将结论引导到同一个最终命题(开玩笑的,千万别以为这是真正的逻辑自洽的定义……)。现给定一个更为复杂的逻辑推理图,本题就请你检查从一个给定命题到另一个命题的推理是否是“逻辑自洽”的,以及存在多少种不同的推理路径。例如上图,从“你遇到难题了吗?”到“那就别担心了”就是一种“逻辑自洽”的推理,一共有 3 条不同的推理路径。
时间限制:7000
内存限制:65536
输入
输入首先在一行中给出两个正整数 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
样例2:
7 8 7 6 7 4 6 5 4 1 5 2 5 3 6 1 3 1 7 1
样例输出
样例1:
3 Yes
样例2:
3 No
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//参考代码1 C++
#include <iostream>
using namespace std;
const int N = 510;
int n, m;
int way[N][N];
int cnt[N], st, en;
bool st1[N], flag = false;
void dfs(int u) {
if (u == en) {
cnt[en] ++;
return;
}
if (way[u][0] == 0) flag = true;
for (int i = 1; i <= way[u][0]; i ++ ) {
int j = way[u][i];
if (!st1[j]) {
dfs(j);
st1[j] = true;
}
cnt[u] += cnt[j];
}
}
int main() {
cin >> n >> m;
for (int i = 0; i < m; i ++ ) {
int a, b;
cin >> a >> b;
way[a][0] ++;
way[a][way[a][0]] = b;
}
cin >> st >> en;
dfs(st);
if (flag) cout << cnt[st] << " No";
else cout << cnt[st] << " Yes";
}</pre><pre class="brush:cpp;toolbar:false">//参考代码2 C语言
#include <stdio.h>
#include <stdlib.h>
#define MAX_NODES 502
int N, M, S1, S2, A, B, consistency, laneNum[MAX_NODES];
int Edge[MAX_NODES][MAX_NODES];
int dfs(int index) {
if (laneNum[index] != 0) return laneNum[index];
for (int i = 0; i < MAX_NODES; i++) {
if (Edge[index][i] != 0) {
if (laneNum[i] == 0) dfs(i);
laneNum[index] += laneNum[i];
}
}
if (laneNum[index] == 0) consistency = 1;
return laneNum[index];
}
int main() {
scanf("%d %d", &N, &M);
for (int i = 0; i < M; ++i) {
scanf("%d %d", &S1, &S2);
Edge[S1][S2] = 1;
}
scanf("%d %d", &A, &B);
laneNum[B] = 1;
dfs(A);
printf("%d %s", laneNum[A], (consistency ? "No" : "Yes"));
return 0;
}</pre>
这道题暂未补解析。