常用算法的模板

欧拉筛法，一种可以在线性的时间复杂度内筛出素数的算法。

把一个图的所有节点排序，使得每一条有向边$(u, v)$对应的$u$都排在$v$的前面。在图论中，这个问题称为拓扑排序(topological sort)。

不难发现：如果图中存在有向环，则不存在拓扑排序，反之则存在。所以可以用拓扑排序来检验是否存在有向环。

一种数据结构，以储存边的方式来存储图。构造方法如下：读入每条边的信息，根据边的起点将边存入对应链表中。通过和链表一样的遍历可以查出以某个点出发的边。除了不能直接用起点终点定位以外，前向星几乎是完美的。

BST（Binary Search Tree）具有以下性质：

1. 若左子树不空，则左子树上所有结点的值均小于它的根结点的值。
2. 若右子树不空，则右子树上所有结点的值均大于它的根结点的值。
3. 左、右子树也分别为二叉排序树。
4. 没有权值相等的结点。

最长上升子序列（LIS，Longest Increasing Subsequence）

“给定n个整数 A1， A2，… ，An，按从左到右的顺序选出尽量多的整数，组成一个上升子序列（子序列可以理解为：删除0个或多个数，其他数的顺序不变）。例如序列1，6，2，3，7，5，可以选出上升子序列1，2，3，5，也可以选出1，6，7，但前者更长。选出的上升子序列相邻元素不能相等”——《算法竞赛入门经典》

（部分解法灵感来源于洛谷题解）