r*******g
发帖数: 1335 | 1 一个棋盘，上面有N种颜色，求最长的同色的circle长度
这道题难道需要从每个点出发做一次dfs？这样会做很多次dfs啊，感觉还有更好的办法。
谢谢了。 |
t*********r
发帖数: 79 | 2 个人感觉可以union find做，假设circle的组成只用上下左右连，不用对角线歇着连
开始每个cell是一个group，对他周围的四个所union，如果是同色的就归为一个group
最后看哪个group里的元素最多 |
r*******g
发帖数: 1335 | 3 但是这个问题是求circle哦，不是求group，或许面试官本来就只要求从一个节点出发
的circle。
group
【在 t*********r 的大作中提到】
: 个人感觉可以union find做，假设circle的组成只用上下左右连，不用对角线歇着连
: 开始每个cell是一个group，对他周围的四个所union，如果是同色的就归为一个group
: 最后看哪个group里的元素最多
|
c*****m
发帖数: 271 | 4 每次dfs visit过的点mark一下，到一个点的时候，如果已经mark为visited的话，就不
用再从它dfs了，复杂度还是O(|V|+|E|)的吧？
有一个问题想问的是：dfs能保证找到最大的circle么？直观感觉是可以的
法。
【在 r*******g 的大作中提到】
: 一个棋盘，上面有N种颜色，求最长的同色的circle长度
: 这道题难道需要从每个点出发做一次dfs？这样会做很多次dfs啊，感觉还有更好的办法。
: 谢谢了。
|
l*3
发帖数: 2279 | |
