并查集模板

缘起

市里面最近有很多犯罪分子, 警方想弄清楚他们之间的从属关系——说白了谁是谁的老大. 但是警方从线人那里只得到了诸如A是B的老大这种零散消息. 警方希望能尽快弄清楚从属关系. 于是并查集诞生了

Read More

无向图的搜索树和森林

缘起

在【1】中，我们论述了图的连通性以及连通分支的概念. 而这里将给出生成树的概念. 无向图的连通分支的生成树是一个极小连通子图. 它包含连通分支所有的顶点，但是只有连通分支顶点个数-1条边. 对于无向图是可以很方便的使用遍历得到其连通分支的生成树的. 因为沿着无向图进行dfs或bfs的话, 得到的就是相应连通分支的生成树。 因为无向图未必连通, 所以我们会得到搜索树构成的森林. 我们可以使用【2】给出的方法将森林转换为树.

所以本文的程序是为了给出图的dfs搜索森林和bfs搜索森林的算法. 注意, 讨论无向图的dfs给出搜索树的目的是为了得到其连通分量（或者叫分支）的生成树. 所以站在生成树的角度讨论有向图的搜索树是无意义的.

Read More

树的三种表示方法

缘起

学习树, 就要知道树的四种表示方法

  1. 双亲表示法
  2. 孩子表示法
  3. 孩子双亲表示法
  4. 长子兄弟法（又叫做二叉树表示法, 因为该方法将多叉树（包括二叉树）转换为了二叉树）

其中，3是值得推荐的. 因为我们将1和2都转换为3

Read More