低年级组集训 第五周：树与图
题单介绍
受各种原因限制（图论知识点较多，考查方式较灵活，难度普遍偏高，常常与其他算法相结合），该专项的题目安排较为杂乱，希望大家以学习和理解概念为主，不要过分因为部分难题钻牛角尖。
图论难度较大，往往与其他算法相结合，在后续的深入学习中，建议大家对下面的各个算法门类进行进一步的研究与深入（如SPFA判负环，差分约束，Floyd动态加点等），并学习其他新算法（连通性算法，二分图算法，网络流初步等）。此外，大家也需要掌握一定的图论建模与转化技巧（例如拆点拆边，超级源/汇，反向建图/补图等）。
## 一、图的存储与遍历
题单：
* [P5318 【深基18.例3】查找文献](https://www.luogu.com.cn/problem/P5318)
* [P2853 [USACO06DEC]Cow Picnic S](https://www.luogu.com.cn/problem/P2853)
## 二、DAG与拓扑排序
该部分的一些知识点在动态规划中出现过（DAG上的DP），这里主要是拓扑排序。
题单：
* [P1113 杂务](https://www.luogu.com.cn/problem/P1113)
## 三、最小生成树
最短路算法有 Kruskal 和 Prim 两种算法，前者的适用范围似乎更广。
题单：
* [P3366 【模板】最小生成树](https://www.luogu.com.cn/problem/P3366)
* [P1194 买礼物](https://www.luogu.com.cn/problem/P1194)
* [P4047 [JSOI2010]部落划分](https://www.luogu.com.cn/problem/P4047)
## 四、最短路
最短路算法分为SPFA，Bellmen-Ford（以及其队列优化形式，即SPFA），FLoyd。
题单：
* [P3371 【模板】单源最短路径（弱化版）](https://www.luogu.com.cn/problem/P3371)
* [P1629 邮递员送信](https://www.luogu.com.cn/problem/P1629)
* [P1462 通往奥格瑞玛的道路](https://www.luogu.com.cn/problem/P1462)
## 五、二分图初步
二分图是一种特殊的图，这种图可以将顶点分成两部分，所有的边都是横跨两个区域的。本次专题中，我们会介绍一下二分图基础与染色，以及二分图最为经典的匹配应用。
* [P1330 封锁阳光大学](https://www.luogu.com.cn/problem/P1330)
* [[2021 ICPC沈阳] Bitwise Exclusive-OR Sequence](https://codeforces.com/gym/103427/problem/B)（本题需到CodeForces平台上完成，洛谷无法远程提交）
* [P2756 飞行员配对方案问题](https://www.luogu.com.cn/problem/P2756)
## 六、树上算法
树上算法的概念较为明了，但是题目难度普遍较高，所以我们只安排了LCA相关题目进入题单，但各位也不要忽视了基础概念的学习与掌握。
提示：“货车运输”一题有hack数据，如果你发现仅有少数测试点无法通过，直接下载hack数据进行debug，或对照题解进行参考即可。
题单：
* [P3379 【模板】最近公共祖先（LCA）](https://www.luogu.com.cn/problem/P3379)
* [P5836 [USACO19DEC]Milk Visits S](https://www.luogu.com.cn/problem/P5836)
* [P1967 [NOIP2013 提高组] 货车运输](https://www.luogu.com.cn/problem/P1967)