> 在hit上看到的
> 我在网上找到一种据说“很经典”的构造方法，没看明白，大家讨论一下吧： 
> 
> 
> 由于每个人都与半数以上的人是朋友，这样就可以用调整法找到一个哈密顿圈。 
> 
> 把人与人的关系看作一个无向图，易证图是连通的。用贪心法找到一条极长路，设其为a1,a2,……,ak。用容斥原理易证有ai(1<i<k)使a1与ak相连且ai+1与a1相连，再连a1-ai+1与ai-ak,使ai与ai+1断开，则这条路变成了一个环。由于图是连通的，从这个环的某处断开必能找到一个更长的极长路，就这样反复找下去，最后那个最大的环就是该图的哈密顿圈。