Posted on 2013-09-04 21:36
happyac 阅读(1702)
评论(0) 编辑 收藏 引用 所属分类:
poj
总结
就是连通性和图的同构判断。
分析
找出属于同一组的点很简单，DFS就可以搞定。图的同构可以用图的Hash来判断。这个不是我想出来的，是网上看来的：
$\sum\nolimits_{i,]} distance(p_i, p_j)$
即同一组中所有点的距离加起来，这个数值做为这个图的哈希值。我不知道如何去证明，但是目前我没找到反例。至少这个题可以用。如果有同学可以帮证明可以或是不可以，那就多谢了。