如何将班级划分为2个部分，每个部分中的每个孩子都是朋友？
如何将班级划分为2个部分，每个部分中的每个孩子都是朋友？
提问于 2020-07-17 16:07:39
如果你想把n个孩子的班级分成两个部分，你知道一些学生成对的学生彼此是朋友，你想试着把这两个部分分开，这样在每个部分中所有的学生都是彼此的朋友。什么是一个有效的算法来形成作为输入n的两个部分，以及形式为‘i和j彼此是朋友’的m个语句。你的算法的运行时间是多少？
我试图将问题建模为一个无向图G，其中有$n$节点，每个子节点代表一个节点。如果两个子节点不是朋友，则两个节点由一条边连接。我们将得到一个包含两个不相交的集合u和v的二部图，其中每个集合中的每个孩子都是彼此的朋友。
这是否足以输出正确的答案？你如何证明它是正确的。
回答 1
Stack Overflow用户
发布于 2020-08-09 03:05:00
你的算法是正确的。如果两个节点是朋友，也可以将这两个节点标记为已连接。在处理完所有的边(朋友关系)之后，执行呼吸优先搜索或深度优先搜索来找出连通组件的数量，在这个问题中，这个数量必须是2。或者，您可以使用Union-Find数据结构来做同样的事情。
上述算法的运行时间均为O(N + M)，N为学生数，M为好友关系数。
证明是非常简单的。我们只需要证明以下两个声明。
- 如果我们可以将所有学生分成两组，那么连接组件的数量必须是2。
- 如果连接组件的数量是2，我们就可以将所有学生分成两组，并满足给定的要求。
为了证明声明1，让我们使用矛盾。假设我们可以将所有的学生分成两组，但是连接的分量数不是2，那么它要么是1，要么是大于2。在任何一种情况下，你总是会得到一个没有完全连接的组。
声明2是不言而喻的。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/62949739
复制相关文章
相似问题
腾讯云开发者
