拓扑排序
拓扑排序拓扑的概念（不重要）知乎上又一篇科普：硬核科普：什么是拓扑？ - 知乎 拓扑学（Topology）原名叫做位置分析（Analysis situs），是研究图形（或集合）在连续变形下的不变的整体性质的一门几何学。由于早期研究的是直观拓扑学，因此人们又把这种研究连续变换下不变的性质的学科形象地称为“橡皮几何学”或“橡皮膜上的几何学”，也就是说橡皮膜在不被弄破的情况下，不管如何拉伸、压缩、扭转等
图论基础
图的相关概念 图论相关定义在不同教材中往往会有所不同，遇到的时候需根据上下文加以判断。 本文章摘录自OI-Wiki，原文地址：图论相关概念 - OI Wiki 图图 (graph)是一个二元组 $G=(V(G), E(G))$。其中 $V(G)$ 是非空集，称为点集 (vertex set)，对于 $V$ 中的每个元素，我们称其为顶点 (vertex)或节点 (node)，简称点；$E
BFS深度优先搜索
BFS的定义BFS(Breadth First Search)，顾名思义就是以广度为优先顺序的搜索算法 矩阵图上的BFS搜索的bfs其实是图上的bfs类比过来的，先看一道图上BFS的题会比较容易理解 3984 – 迷宫问题 定义一个二维数组： 1234567int maze[5][5] = { 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0,
倍增
和双指针一样，倍增也是一种解决问题的思想，不局限与某种特定题型，只要是能用到长序列的情况，都有可能用到倍增算法，需要我们能够敏锐得发现题目中的特性，利用倍增思路解决问题。 倍增法（英语：binary lifting），顾名思义就是翻倍。它能够使线性的处理转化为对数级的处理，大大地优化时间复杂度。 RMQ问题RMQ问题，即Range Minimum/Maximum Query（区间最大&#
双指针
双指针顾名思义，就是同时使用两个指针，在序列、链表结构上指向的是位置，在树、图结构中指向的是节点，通过或同向移动，或相向移动来维护、统计信息。 双指针不能算一个真正意义上的算法，而是一种编程技巧，一种解决问题的优化思路 这里介绍两种比较常用的双指针的应用场景：维护区间信息和利用序列有序性 维护区间信息P1147 连续自然数和 - 洛谷 对一个给定的正整数 $M$，求出所有的连续的正整数段（每一
二分查找、二分答案、三分
二分查找 二分查找主要解决有单调性的序列问题 问题背景给定一个有序数列，例如{1, 3, 4, 5, 7, 9, 10, 11, 12, 13, 15, 16, 19, 20, 22, 23}，要你通过程序找到$11$这个数所在的位置，如果没找到则输出$-1$ 一个比较容易想到的方法是，从前往后枚举，知道当前枚举到的值与$11$相等，则跳出循环 1234567int key
图的匹配
图的匹配相关概念匹配 或是 独立边集 是一张图中不具有公共端点的边的集合。在二分图中求匹配等价于网路流问题。 图匹配算法是信息学竞赛中常用的算法，总体分为最大匹配以及最大权匹配，先从二分图开始介绍，再进一步提出一般图的作法。 图的匹配在图论中，假设图 $G=(V,E)$，其中 $V$ 是点集，$E$ 是边集。 一组两两没有公共点的边集 $M(M\in E)$ 称为这张图的 匹配。 定义匹
连通性相关问题题解
[P2341 USACO03FALL / HAOI2006] 受欢迎的牛 G - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666