Number of Islands那道题用Union Find的优点在哪？比起BFS

今天专门去看了眼number of islands ii, 还是得用union find 做. 做的最快那个熏呆确实做得挺好的.. 用1d array找爸爸

number of islands 1 是体现不出 dfs 和 ufds的差别的, 所以也问不出个所以然来..

这种搜索题DFS/BFS都能做，但是这两种方式其实都把路径给一起算了，题目本身并没有要求知道路径，只要知道一个连通性就够了，所以UF的价值在这里，而且UF一集合好，一查就完了，不太容易出错。。

pxu 发表于 2018-6-11 10:59
我不知道dfs怎么解决，用island1的思路去做超时了。
uf不会忘了是指我记得UnionFind Class怎么写，这部分 ...

感谢分享～
但是如果加之前加过的点（比如[[0,0],[0,1],[1,2],[1,2]]）需要额外处理一下，在你的代码基础上加上：
if (grid[p[0]][p[1]] == 1) {
               res.add(res.get(res.size() - 1));
               continue;
           }
就可以AC了。

我请教过高手，告诉我这样：dfs能做的通常先用dfs，一般速度路略快。有的题dfs不行，必须bfs。uf对特殊问题效率高（比如island 2里cell不断地增加)，uf只需对付新增的部分即可，对付这些问题就要用uf.

想请教一下，像这种搜索matrix的题目，如果说给的1 都是很接近彼此，而不是分散在matrix里，那是不是用bfs比较好？有没有同学可以解释一下像这种搜索的题目，什么时候用bfs，或者dfs比较好？ 谢谢！

X88 发表于 2019-09-23 19:39:59
我请教过高手，告诉我这样：dfs能做的通常先用dfs，一般速度路略快。有的题dfs不行，必须bfs。uf对特殊问题效率高（比如island 2里cell不断地增加)，uf只需对付新增的部分即可，对付这

怎么觉得应该先优先bfs > dfs，因为可以提前退出，尤其是找最短路径之类的