In a kindergarten, there are a lot of kids. All girls of the kids know each other and all boys also know each other. In addition to that, some girls and boys know each other. Now the teachers want to pick some kids to play a game, which need that all players know each other. You are to help to find maximum number of kids the teacher can pick.
这是一道求最大团的问题，我们可以转化成求补图的最大独立集。我们可以注意到，原图的补图实际上是一个二分图。因为对于男生集团和女生集团，不同种集团内部都没有边相连，只存在一段在男生集合，一段在女生集合的边。这篇文章分析过，二分图的最大独立集 = N - 最大匹配，所以我们只需要找最大匹配即可。时间复杂度O(V * E)，代码如下：
No comments:
Post a Comment