问题来自Code jam .
问题:
有什么方法可以将图形的节点分成两组,使得不能留在同一组中的任何两个节点应该在不同的组中。
这有什么标准算法吗?
当每个组应该有相等的元素时,我应该如何解决这个问题。
最佳答案
首先,可行性问题(是否存在这样的集合/不存在这样的集合)是2-coloring problem ,其中:
G = (V,E)
V = { all nodes }
E = { (u,v) | u and v are "troubling each other" }
这个问题通过检查图是否为bi-partite来解决, 并且可以使用 BFS 来完成.
How to tackle the problem when each group should have equal element.
首先,我们假设该图是二分图,因此有一些解。
将图拆分为一组连通分量:(S1,S2,S3,...,Sk)
。
每个连通分量实际上是一个子图 (Si = Li,Ri) - 其中 Li,Ri 是二分图的两侧(如果忽略 Li 和日)。
创建一个新数组:
arr[i] = |Li| - |Ri|
where |X| is the cardinality of X (number of elements in the set)
现在,解决此问题与解决 partition problem 相同,这可以在伪多项式时间内完成(这是节点数的多项式)。
分区问题的解决方案将每个 arr[i]
拆分为 A
或 B
,这样 sum{ A}
尽可能接近 sum{B}
。如果 arr[i]
在 A
中,在您的解决方案中,为 Li
着色“1”,为 Ri
与“2”。否则 - 做相反的事情。
解决方案将是O(k*n+m)
,其中k
是连接组件的数量,n
是节点的数量图形,m
是图形中的边数。
关于algorithm - 将图形分成两组,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32054053/