这是一个很容易解释的问题，但我在找出解决方案时遇到了一些困难。我最喜欢的那种!
让 G=(V,E) 成为一个二部图。我需要计算最小子集 V'，以便对于每条边 e=(u,v)，u 属于 V' 或 v 属于 V'。 如果有不止一种解决方案，任何人都可以接受。
|V| <= 2000
|E| <= 10000
任何提示都可能有用:D
最佳答案
Konig's theorem是相关的。
关于algorithm - 从每条边中选择一个顶点，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8230581/