总结一下二分图匹配的几种算法

因为参加在上海举办的计算机设计大赛决赛，今天没事所以去了上海科技馆，我们观赏了多个展区之余尝试突破展览馆中计算机展览程序的沙盒，并玩一盘扫雷游戏。

有向图的强连通分量是一个极大强连通子图。一个强连通子图是一个节点集合，使得集合中的任意两个点互相可达。本文介绍有向图强连通分量的tarjan算法，并且提供了理解tarjan算法所需要的前置DFS知识。
直观上来讲，tarjan算法对有向图建立搜索树，每一个连通分量都是该搜索树的一棵子树。在无向图中查找连通分量时，我们常借助于dfs，那么在有向图查找强连通分量时，我们也使用了借助于dfs的tarjan算法。tarjan算法由一个dfs构成，在dfs过程中，将访问过的节点压入一个栈中，栈顶到栈中的的某个元素构成一个极大强连通分量。

一个动态分配器的要求是：

1. 处理任意请求序列
   这意味着我们不能对请求的先后顺序以及释放操作发生的时间（甚至是否发生）做出任何假设。
2. 立即响应
   这里不是指要实现无阻塞的分配，而是说我们的请求要是在线的，我们不能进行缓冲或者重排
3. 使用堆
4. 对齐
5. 不能移动已分配的块

一个动态分配器的目标包含下面两点，我们能看到的是这两个性质往往互为trade-off。

1. 最大化吞吐率
2. 最大化存储器利用率

【未完待续】

对 Effective C++ 在资源管理部分的内容进行总结。这一部分其实已经比较基础了，等待重构。

flex/bison是对lex/yacc的开源实现，可以方便地进行编译器构造。MSVC下的flex和bison有着win_flex和win_bison这两个封装，用起来比较方便。
本文就使用flex和bison进行编译器构造时出现的一些问题进行说明，并讨论一些进阶技巧，例如重定向输入流，处理大小写不敏感代码串，yymore，代码定位，错误信息及恢复，start condition，扩栈，push parser，glr-parser，%define指令，常见语法和错误处理方法以及flex/bison生成代码分析等。

1959年，Chomsky证明了文法和自动机的等价性，由此形式语言诞生了。目前，我们主要探讨4类文法，正则文法（确定有限自动机或非确定有限自动机）、上下文无关文法（下推自动机），上下文有关文法（线性有界自动机）、无限制文法（图灵机）。
有限自动机具有有限种状态。
上下文无关文法(CFG, Context Free Grammar)属于二类文法，其能力等价于下推自动机(PDA)。相对于三类文法即正则文法，上下文无关文法能够对非终结符做状态转移。
图灵机的状态也是有限的。图灵机的“内存”不是栈，而是纸带，由此可以看做是有两个栈的PDA。
自上而下和自下而上是两种常用的上下文无关文法分析方法。
自上而下的方法的难点在于选择哪个产生式进行推导，自下而上的分析方法难点在于在不同的格局下选择移进或归约的矛盾。

线段树和树状数组是一系列神奇的数据结构的起源，但其本身却十分简洁优雅，是我非常喜欢的两种数据结构。

浙江大学PAT(Programming Ability Test) A-level、top-level以及CCCC练习题的部分解题报告。
源码在 https://github.com/CalvinNeo/PAT

[YN\d]\t(\d\+\-)+\t([\w ]+)\(\d+\).*

五月八日在南京大学参加了第一届江苏省程序设计大赛。这次破天荒拿了7A。