好书好书

在看《数据结构与算法分析》这本书的时候看到后面的一个关于并查集的有趣应用，是个生成迷宫的算法，看起来非常有趣，所以就实现了一下。顺便把几种走迷宫的算法都整了 进去。八卦一下，这本书的作者是Mark Weiss,这牛写了几本数据结构和算法的书，各种语言版本 (C,C++,Java)，原来是师出名门啊，在他的主页上一看，原来是Robert Sedgewick 的学生。Sedgewick 更是师出名门，在 Princeton 跟高纳德神牛读的博士，也写了 N 本算法和数据结构的书。这两人写的书都还不错，对于初学者和中等水平来说很好，覆盖了一般的数据结构和算法，同时带有一定的理论分析还有特定的语言实现。

并查集

可能一般的大学教材上面没有说这个数据结构，这是个很有趣的东西。《算法导论》上面用这个来作为均摊分析的例子吧。在 ACM/ICPC 中这个数据结构经常出现，有可能是一个小题（难点的就是要维护节点之间关系的那种），或者是有的图论算法中实现要用，比如实现 Kruskar 算法求最小生成树。
并查集本身比较简单，主要是用来操作元素集合，支持的操作有：

一并一查，所以叫作并查集。实现时候可以通过按秩合并 (union by rank)，和路径压缩 (path compression) 来增加效率，可以获得几乎与总操作数 m 成线性关系的运行时间。

int rank[MAXSIZE];    // 节点高度的上界
int parent[MAXSIZE]; // 根节点

void Init(void){
  memset(rank, 0, sizeof(rank));
  for(int i=0; i < MAXSIZE; ++i )
    parent[i] = i;
}

int FindSet(int x){// 查找 + 递归的路径压缩
  if( x != parent[x] )
    parent[x] = FindSet(parent[x]);
  return parent[x];
}
​
void UnionSet(int root1, int root2){
  int x = FindSet(root1), y = FindSet(root2);
  if( x == y ) return ;
  if( rank[x] > rank[y] ) parent[y] = x;
  else{
    parent[x] = y;
    if( rank[x] == rank[y] ) ++rank[y];
  }
}

迷宫的实现

上面那本书上的习题上给了提示，比如首先所有的墙都没有去掉，那么是一个一个的方格，每一个方格为并查集合的一个元素，已经连通的元素是在并查集的一个集合中，有相同的根节点。随机的选择一个墙，在并查集中查询这两个元素是否已经连通，如果已经连通则另选一个墙，如果不连通，union 两个节点的根节点，这样操作以后这两个方格已经连通。继续上面的操作，直到入口和出口连通位置，那么这就形成了一个只有一条合法路径的迷宫，称为单迷宫。如下图所示。

左上角起点 右下角终点