0x60 图论

在本章中，我们将探讨图论的相关算法与题目模型。0x61节和0x62节介绍最短路、最小生成树这两个经典模型及其扩展。0x63节和0x64节探讨一些树上的问题，同时扩展到基环树等变体结构。0x65节介绍最短路中负环的判定方法以及差分约束系统。0x66节和0x67节介绍图连通性的Tarjan算法与相关模型，包括割点、割边、双连通分量、强连通分量、2-SAT、欧拉路等。0x68节和0x69节主要介绍二分图，包括二分图最大匹配、最小点覆盖、最大独立集、最小路径覆盖等。0x6A节初步涉及网络流的内容，使读者开拓眼界，对网络流的概念与简单应用有基本的了解。图论涉及的内容广泛、形象、实际，知识体系的综合性较强，还融合了之前学习的各类算法与数据结构。在数学与信息科学中，图论既有悠久的研究历史，也不失新兴的应用价值，一直是程序设计竞赛的重要关注点。