第一个想法是就直接去归类,使用两个集合根据关系把这些点放入集合,看看是否能分类成功
提交之后发现效率太低,超时了
转换思路,改用在图里面找loop的方式A不喜欢B,B不喜欢CC不喜欢D,D不喜欢EE不喜欢A。如果分成两类的话在A的这边就会造成一个内部的循环。只要存在类似的loop那么就是False。通過DFS的方式可以走遍整个图但是图可能是不连通的,所有需要根据每个节点来做一次dfs
第一个想法是就直接去归类,使用两个集合根据关系把这些点放入集合,看看是否能分类成功
提交之后发现效率太低,超时了
转换思路,改用在图里面找loop的方式A不喜欢B,B不喜欢CC不喜欢D,D不喜欢EE不喜欢A。如果分成两类的话在A的这边就会造成一个内部的循环。只要存在类似的loop那么就是False。通過DFS的方式可以走遍整个图但是图可能是不连通的,所有需要根据每个节点来做一次dfs
版权声明:文章内容来源于网络,版权归原作者所有,如有侵权请点击这里与我们联系,我们将及时删除。