刷题刷出新高度,偷偷领先!偷偷领先!偷偷领先! 关注我们,悄悄成为最优秀的自己!

简答题

那就别担心了

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

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

使用微信搜索喵呜刷题,轻松应对考试!

答案:

这是一个图论和深度优先搜索(DFS)的问题。首先,我们需要构建一个命题关系图,然后使用DFS来搜索从命题A到命题B的所有路径。在DFS过程中,我们需要记录路径的数量以及是否存在循环依赖。最后根据搜索结果判断推理是否逻辑自洽并输出路径数量。

主要步骤包括:

  1. 构建命题关系图:使用邻接表或者邻接矩阵来表示命题之间的关系。
  2. 深度优先搜索:从命题A开始,搜索所有可以到达命题B的路径。
  3. 记录路径数量和循环依赖:在DFS过程中,记录路径的数量,并检查是否存在从某个命题出发可以推导出该命题自身的情况,即循环依赖。
  4. 判断逻辑自洽性:如果所有路径都可以成功推导到命题B,并且没有循环依赖,那么推理是逻辑自洽的。
  5. 输出结果:输出路径数量和逻辑自洽性的判断结果。

解析:

对于此类问题,首先需要理解题目中的"逻辑自洽"的含义。逻辑自洽指的是从一个命题出发的所有推理路径都会将结论引导到同一个最终命题,且在推理过程中不存在循环依赖。因此,我们需要使用图论的知识来构建命题之间的关系图,并使用深度优先搜索来寻找所有的推理路径。

在C语言中,我们可以使用结构体来表示图的结构,然后使用递归的方式实现深度优先搜索。在搜索过程中,我们需要记录路径的数量以及是否存在循环依赖。最后,根据搜索结果判断推理是否逻辑自洽,并输出路径数量和判断结果。

创作类型:
原创

本文链接:那就别担心了 下图转自“英式没品笑话百科”的新浪微博 —— 所以无论有没有遇到难题,其实都不用担心。

版权声明:本站点所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。

让学习像火箭一样快速,微信扫码,获取考试解析、体验刷题服务,开启你的学习加速器!

分享考题
share