拓扑排序 定义 对一个有向无环图 (Directed Acyclic Graph 简称 DAG) G 进行拓扑排序，是将 G 中所有顶点排成一个线性序列，使得图中任意一对顶点 u 和 v，若边 ∈ E(G)，则 u 在线性序列中出现在 v 之前。通常，这样的线性序列称为满足拓扑次序 (Topological Order) 的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。 ——百度百科 步骤 由 AOV 网构造拓扑序列的拓扑排序算法主要是循环执行以下两步，直到不存在入度为0的顶点为止。 ...

搜索 DFS · 深度优先搜索 定义 深度优先搜索属于图算法的一种，英文缩写为 DFS 即 Depth First Search. 其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。 ——百度百科 在一条路上的分岔按顺序选择方向，一条路走到底再返回到最近分岔选择下一条路，这个分岔下所有路全走完后再返回到更上一个分岔走下一条路。 基本思路 深度优先遍历图的方法是，从图中某顶点v出发： 1. 访问顶点 v ； 2. 依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的...

二分查找 简介 二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。 ——百度百科 有序排列 sort (a + 1, a + n + 1, cmp); 时间复杂度 O(logn) 学了二分以后给我的感觉就是很多东西都可以拿来二分，以前以为只有查找可以用二分，现在知道原来很多有范围的东西，都可以用二分来逼近答案。 整数二分 找 >= s 的数中最小的 记录答案 bool ch...

并查集 并查集是一种树型的数据结构，用于处理一些不相交集合（disjoint sets）的合并及查询问题。常常在使用中以森林来表示。 ——百度百科 主要操作 初始化 int f[N]; void Init(int x) { for (int i = 1; i <= x; i++) f[i] = i; } 使所有元素都指向自己，将自己作为父节点 查找 int Find(int x) { if (x == f[x]) return x; ...

基础知识 常用 OJ Vjudge nowcoder PTA 常用语言 - C++ 终于用回 C++ 了，上程序设计基础转 C 好累 万能头文件 #include 等于以下头文件： #include #include #include #include #include...