我有以下问题
输入看起来像这样:
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。
最佳答案
使用不相交集数据结构获取由同意
导出的图的连通分量。
这会导致顶点 (=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
并且包含人的顶点有相同的颜色否
否则
关于java - 需要帮助来创建算法,根据人们的意见将他们分组,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37046976/