**Codeforces图论题单 **

【CF 1200-1600 - 图论】(基础遍历与简单路径)

• CF520B Two Buttons (BFS / 从目标逆向搜索)
• CF20C Dijkstra? (经典Dijkstra)
• CF723D Lakes in Berland (BFS/DFS求连通块大小并排序删除)
• CF977E Cyclic Components (DFS/BFS判断连通块是否为简单环)
• CF115A Party (DFS/BFS求森林中树的最大深度，表示层级)
• CF1020B Badge (DFS/模拟，每个点出发必然进入一个环)
• CF500A New Year Transportation (简单DFS/BFS判断图上可达性)
• CF580C Kefa and Park (树上DFS/BFS，路径上连续猫的数量限制)
• CF687A NP-Hard Problem (二分图染色)
• CF1167C News Distribution (并查集维护传递闭包/社交网络)
• CF771A Bear and Friendship Condition (并查集/DFS，判断每个连通块是否为完全图)
• CF1006E Military Problem (DFS序 + 二分查找子树中的第k个节点)
• CF1389B Array Walk (简单DP，但在图上看作带限制的移动)
• CF1325C Ehab and Path-etic MEXs (树的构造，利用叶子节点性质分配边权)
• CF1237B Balanced Tunnel (拓扑排序思想 / 找必须等待的车辆)
• CF437C The Child and Toy (贪心，按点权从大到小（或相反）考虑贡献)
• CF1092B Teams Forming (排序后两两配对)
• CF1334B Middle Class (排序贪心，从富的开始补贴)
• CF1342B Binary Period (字符串构造，和图关系不大但常一起出现)
• CF1365B Trouble Sort (判断数组是否有序或是否有0和1同时存在)
• CF1249B2 Books Exchange (hard version) (置换环分解，求每个元素所在环长)
• CF1373C Pluses and Minuses (前缀和，模拟过程，找到最早非法时间)
• CF472A Design Tutorial: Learn from Math (构造合数和)
• CF1303B National Project (贪心，计算最少天数)
• CF1144C Two Shuffled Sequences (构造两个单调序列)
• CF1093B Letters Rearranging (判断回文串或构造非回文)
• CF939A Love Triangle (暴力枚举三元环)
• CF1358B Maria Breaks the Purity (贪心，从弱的开始尝试能否形成团体)
• CF1201A Important Exam (按位贪心选择答案)
• CF1256A Payment Without Change (简单数学判断)

【CF 1600-2100 - 图论】(常用图算法与模型)

• CF540C Ice Cave (BFS，需要仔细处理起点终点相同和冰块状态)
• CF191C Fools and Roads (LCA + 树上差分统计边经过次数)
• CF920E Connected Components? (BFS/DFS，用std::set维护未访问邻居高效找边)
• CF1100E Andrew and Taxi (拓扑排序 + 二分答案检查是否存在负环思想的路径)
• CF427C Checkposts (Tarjan求SCC，统计最小代价和方案数)
• CF337D Book of Evil (树形DP / 两次DFS求树上距离某点集合最远的点)
• CF1027D Mouse Hunt (基环树森林，找每个基环树上权值最小的点（环上）)
• CF510C Fox And Names (拓扑排序，根据字符串相对顺序建图)
• CF449B Jzzhu and Cities (Dijkstra + 考虑修建火车线路的特殊边)
• CF1076D Edge Deletion (Dijkstra树/BFS树，从根出发保留k条最短路径树的边)
• CF1213G Path Queries (Kruskal重构树思想 / 并查集按边权从小到大加边离线处理)
• CF721C Journey (DAG上DP，限制边数的拓扑排序求最长路)
• CF1305D Kuroni and the Celebration (交互题，通过查询两点LCA逐步缩小范围找根)
• CF1009D Compatible Numbers (构造一个边数尽可能多的图，满足任意两点路径上边权GCD为1)
• CF118E Bertown roads (Tarjan找桥，然后在DFS树上给边定向构造强连通（除了桥）)
• CF839C Journey (树上期望DP / DFS计算期望长度)
• CF601A The Code (分层图最短路 / BFS，不同交通工具看作不同层)
• CF1245D Shichikuji and Power Grid (最小生成树，建立超级源点处理建发电站的代价)
• CF1033C Permutation Game (记忆化搜索 / 博弈DP，建图表示能跳到的位置)
• CF1202E You Are Given Some Strings... (AC自动机 + fail树上DP/贡献统计)
• CF938D Buy a Ticket (Dijkstra变形，每个点可以先飞到某个城市再买票)
• CF1340B Nastya and Scoreboard (数位DP / 贪心，匹配数字亮灯)
• CF475D CGCDSSQ (莫队 / 分治 + ST表/GCD，统计区间GCD为特定值的子区间) - 虽然不是纯图论
• CF1380D Berserk And Fireball (贪心 / DP，处理区间清除操作) - 同上
• CF1091D New Year and the Permutation Concatenation (组合计数 / DP，分析排列性质)
• CF1198B KMP Algorithm (KMP的fail树是图论结构，这里是字符串题但用了KMP)
• CF1328E Tree Queries (LCA判断路径包含关系)
• CF1207F Remainder Problem (根号分治处理查询和修改) - 同上
• CF1140D Minimum Triangulation (简单多边形三角剖分DP)
• CF1062E Company (树上倍增LCA + DSU on tree/线段树维护子树信息)

【CF 2100-2500+ - 图论】(高级图算法、复杂建模与混合问题)

• CF487E Tourists (圆方树 / 点双连通分量 + 树链剖分/LCT维护路径最小值)
• CF786B Legacy (线段树优化建图 + Dijkstra)
• CF603E Pastoral Oddities (LCT维护动态最小生成森林 / 整体二分 + 可撤销并查集)
• CF700C Break Up (网络流求割边和最小割 / Tarjan)
• CF1081E Missing Numbers (构造，利用平方差公式，图论关联较弱但常出现在这个难度)
• CF840C On the Bench (组合计数DP，处理相同元素不相邻，容斥)
• CF1148F Foo Fighters (构造 / 按位贪心，利用异或性质)
• CF915F Stas and the Queue at the Buffet (Kruskal重构树 / 启发式合并维护连通块信息)
• CF1045A Last Chance (网络流最大权闭合子图 / 最小割，武器与怪物模型)
• CF1270F Awesome Substrings (根号分治 / 字符串哈希 + map)
• CF1100F Ivan and Burgers (线性基求区间异或最大值) - 数据结构，但常与图论结合
• CF1137C Museums Tour (Tarjan缩点 + DAG上分层图DP/最长路，考虑星期)
• CF997B Roman Digits (打表找规律 / BFS状态搜索)
• CF576D Flights for Regular Customers (bitset优化图上DP / 矩阵快速幂求可达性)
• CF1280C Divide and Conquer (树形DP，计算每条边对两种答案的贡献)
• CF802N Send Boxes to Alice (WQS二分 / 费用流，凸优化DP)
• CF1060E Sergey and Subway (换根DP / 计算每条边对总路径长度的贡献)
• CF1208G Polygons (最小表示法 / KMP思想求循环节) - 字符串
• CF1039D You Are Given a Tree (长链剖分优化树形DP / 根号分治按k值处理)
• CF1019C_Tree_Generator (构造，利用度数性质和DFS)
• CF1174E Ehab and the Expected GCD Problem (期望DP，质因数分解)
• CF986C AND Graph (并查集 / DFS，按位建图的连通性)
• CF757E Bash Plays with Functions (数论函数 + DP/记忆化搜索)
• CF555E Case of Computer Network (树上差分 + Tarjan边双缩点，判断边是否必须同向)
• CF1080F Vova and Train (二分答案 + 主席树/二维数据结构判断区间是否有可用列车)
• CF1307E Cow and Vacation (网络流/费用流建模，或者贪心+DP)
• CF1290D Coffee Varieties (hard version) (交互题，巧妙分组查询)
• CF1023F Mobile Phone Network (Boruvka算法思想 / Kruskal + LCA)
• CF1187E Tree Painting (换根DP)
• CF1054E Chips Puzzle (构造，把棋子移动到指定位置，类似华容道)