java - 需要帮助来创建算法，根据人们的意见将他们分组

Question

我有以下问题

输入看起来像这样:

agree 1 2
disagree 2 3
? 1 2
? 1 3
agree 1 3
? 4 5
agree 0 5

等等。数字代表人(编号从 0 到 n)。同意意味着那两个人有相同的意见(我不知道是正面还是负面，我只知道是一样的)。不同意意味着他们有不同的意见。？是程序必须回答的问题，即这两个人的意见是否相同。

此特定输入的输出应如下所示:

yes
no
error
don't know

是的，因为第一个问题是 1 和 2 是否与他们基于第一行输入的意见相同。no 是因为 1 和 3 的意见不同，因为我们可以看到 1 同意 2 而 2 不同意 3 所以 1 必须不同意 3。错误是因为我们得到的输入是 1 与 3 一致，我们知道这是一个谎言，所以我们打印出错误。不知道是因为最后一个问题是关于之前没有提到的4和5，所以我们不知道他们的意见。

所以我的想法是创建一个类 Person 并给它们属性:数字和颜色(用于意见)但后来我意识到这在我将不连接组的情况下不起作用，例如 1 2 同意，4 5同意然后我会问如果 2 4 同意，我不应该知道答案但他们会有相同的颜色..

我的问题是，您能否帮我找出存储每个人意见信息的最佳方式，最好是使用 Java 或 Python。

Answer 1

使用不相交集数据结构获取由同意导出的图的连通分量。

这会导致顶点 (=persons) 的分区 P = {P_1, P_2, ..., P_n}

然后考虑下图:

G = (P, {(A, B) ∈ P² | ∃ a ∈ A, b ∈ B: disagree(a, b)})

即新图中有 2 个分区相连，当且仅当节点之间有 2 个顶点不一致。

现在可以得到如下结果:

• 不知道这些人是否不在 G 中属于 G 的连通分量的顶点内
• 否则，对包含 G 中两个人的连通分量进行 2 色着色。结果为:
  • error 如果连通分量中有任何 2 个顶点包含不同意的人，或者连通分量没有 2 种颜色
  • yes 如果不是error 并且包含人的顶点有相同的颜色
  • 否否则