long龙8国际中文网

一个关于 编程问题的解答网站.

有 Java 编程相关的问题?

你可以在下面搜索框中键入要查询的问题!

java提供了一种算法,在给出形式为R(x,y)的断言列表的情况下,检查两条狗x和y是否具有相同的品种

我这学期要上算法课,期中考试就要到了。有一个关于过去期中考试的问题。我们得到了一个n条狗的列表和一个形式为R(x,y)的m断言的列表,这意味着x和y具有相同的品种。给出了R是一个等价关系。给定两条狗x和y,我们需要制定一个算法来确定它们是否有相同的品种。 最简单的方法是查看断言列表,检查断言对(x,y)是否存在,但这并不能在所有情况下都有效

假设我们有Dogs={a,b,c,d}和断言={(a,b),(b,d)}。我们被要求检查a和d是否有相同的品种。设计这个算法的好起点是什么


共 (1) 个答案

  1. # 1 楼答案

    让我们把这个输入解释为一个图形,每只狗都是顶点,输入是两条狗之间的边,如果它在一个组件中,你的答案将是真的,显然你可以用DFS算法找到所有组件