接着BFS写
看课后神题吧
把邻接表换成矩阵 复杂度会发生什么变化。 初始化还是O(V)，while那个地方也是O(V)次但是每个while内部的的for变成了每次都要找O(V）次去确定边，所以while的总花费是O(V2) 最后是O(V2) 。
矩阵除了名人和屌丝问题 很难摆脱O(V2)的限制
这题真心看了好几遍才看懂题是什么意思
Have n professional wrestler {1,2,3,4,5...N}
list of r pair like{ {1,2},{3,5},{2,3} ...}
要解决的是个deterministic 问题 针对这两个输入，用O(n+r)时间确定是否存在 一种对wrstler的分租 一组好人 一组坏人，这样针对那个r pair 永远是好人对抗坏人
例如 这对 {1,2,3} {(1,2),(2,3),}这样的输入 就存在 1是好人 2是坏人 3是好人 就可以了
如果 {1,2,} {(1,2),(2,3),(31)} 这个就不行 1是好人 2 是坏人 3是好人 这样1就必须是坏人 contradiction
好， 我们把 wrestle 集合映射为我们的G.V集合 大小为n, 而pari集合映射为G.E集合,大小为r
下一步的思路就是既然是要确定是否存在，那咱怎么也得把整个G逛一遍吧， 选个BFS逛一遍。
恩，下一步确定在逛的过程中，怎么收集信息和判断咱们的结论，我们为每个点分配一个变量 FLAG= {good，bad}；
然后如果存在(u,v)那么v.flag = u.flag 取反 。 这样的话看起来很简单 遇不到矛盾啊。
那是因为我们只完成了设置信息这一步，还没有完成收集和判断信息。
我们观察一下 如果根据E集合 确定的是一个没有回路和交叉的树， 就不会存在contradiction， 当然发生了回路和交叉，也不一定发生contradiction。
但是发生了contradiction 一定是发生了回路或者交叉。
所以我们的focus定位为 meet vertex color not WHITE
然后进行判断，因为not white 代表访问过了，也就意味着角色已经确定了，但是因为这个back edge 又会对这个black vertex 有一个新角色的任命， 当然如果这一次的任命和他现在的角色一样，就没有contradiction，如果不一样，那就呵呵了，没有办法分配角色，谁规定的这个匹配pair的E 找他算账去吧。
恩 我们稍微改一些BFS就可以了
看到这题的第一感觉是用DP去解，因为是求最优解，思路就是运行V次BFS 算出每个V的SPF 然后再选出期中最大的一次
复杂度为O(V(V+E))
看到一种很漂亮的解法只用了O(V+E）就解出了
思路和后面的拓扑排序很像。
用一次BFS，然后从最后记录的那个点再用一次BFS跑到的该次BFS中的最长树高就是答案
只跑了两次BFS 时间是O(V+E)。
思路很简单 因为是无向图处理，所以第一次任意选的点
1.位于直径上，那第一次就得到最大了，第二次保持不变
2.不位于直径，位于中间的圈，那第一次的BFS的终点一定是圆心的圈，那么从圆心的圈运行BFS就一定能找到圆心到直径圈的的BFS tree。
这题就是著名的欧拉回路问题，也是一笔画问题，如何一条边只遍历一次，走出迷宫。
给了很多硬币。
本质就是高效的遍历问题，用硬币的正反面代替咱们的WHITE and BLACK 在BFS里即可