洛谷 P1141 01迷宫

题目： 01迷宫

显然，题目要求我们对于给定的图求联通块大小，用DFS或并查集可过.

解法1：DFS+记忆化

这种做法要求询问时进行DFS，稍显麻烦.

解法2：并查集

两次预处理，分别对横向和竖向进行union操作.

在预处理时，每次查根的时间近似 $O(1)$.

预处理时间复杂度 $O(n^2)$.

对于每个查询，消耗时间近似 $O(1)$，总时间复杂度 $O(m)$.

估测一下，总时间大约是 $2 \times (10^3) ^ 2 + 10^5$，即$10^6$的数量级，可行.

代码：unionfind.cpp