java - 一种算法，用于检查 2 只狗 x 和 y 是否具有相同品种，给出 R(x,y) 形式的断言列表

Question

关闭。这个问题需要多问 focused 。目前不接受答案。

---

想要改进此问题吗？更新问题，使其仅关注一个问题 editing this post .

已关闭 3 年前。

Improve this question

这学期我正在上算法课，我们即将迎来期中考试。刚刚过去的期中考试有一道题。我们得到一个包含 n 只狗的列表和一个包含 m 个断言的列表，其形式为 R(x,y)，这意味着 x 和 y 具有相同的品种。已知R是等价关系。给定 2 只狗 x 和 y，我们需要制定一个算法来确定它们是否具有相同的品种。最简单的方法是检查断言列表并检查 (x,y) 对是否存在，但这并不适用于所有情况。

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

Answer 1

让我们将此输入解释为一张图，每只狗将是顶点，输入将是两只狗之间的边，如果它在一个组件中，您的答案将为真，显然您可以使用 DFS 算法找到所有组件。