Graph 图论

  • 前向星
  • 图的割点、桥
  • 双连通分量
  • 有向图的强连通分量
  • 无向图连通分支
  • 拓扑排序
  • 2-SAT
  • 染色概念、完美消除序列
  • 第K短路
  • 哈密顿路、欧拉路径、欧拉回路
  • DAG的深度优先搜索标记
  • 独立集、团、支配集概念
  • 最大团问题
  • 弦图判断
  • 弦图的PERFECT ELIMINATION点排列
  • 稳定婚姻问题
  • 有向图最小点基
  • Floyd求最小环

============================以下是最大团&稳定婚姻系列============================
【HDU】

1530 Maximum Clique
1435 Stable Match
3585 maximum shortest distance 二分+最大团
1522 Marriage is Stable
1914 The Stable Marriage Problem

【POJ】

1129 四色定理 着色问题
1419 最大独立集
2989 极大团
3487 The Stable Marriage Problem 稳定婚姻
============================以下是强双联通系列============================
【HDU】
强连通:
1269 迷宫城堡 判断是否是一个强连通
2767 Proving Equivalences 至少加几条边让整个图变成强连通
3836 Equivalent Sets 至少加几条边让整个图变成强连通
1827 Summer Holiday 传递的最小费用
3072 Intelligence System 传递的最小费用
3861 The King’s Problem 强连通+二分匹配
3639 Hawk-and-Chicken 强连通缩点 + 树形dp（累加子节点的总权值）
3594 Cactus 仙人掌图

双连通:
2242 考研路茫茫——空***室 双联通缩点+树形DP
2460 Network 边双连通
3849 By Recognizing These Guys, We Find Social Networks Useful 双连通求桥
3896 Greatest TC 双连通
4005 The war 边双连通

LCA:
2586 How far away ？
2874 Connections between cities
3078 Network LCA+排序
3830 Checkers 二分+LCA

【POJ】
强连通:
1236 Network of Schools
2553 The Bottom of a Graph 好题！ 找出度为0的集合
2186 Popular Cows 好题！ 找出度为0的，其他分量都指向它的集合
2375 Cow Ski Area 强连通
2762 Going from u to v or from v to u? 缩点+拓扑排序
3160 Father Christmas flymouse 强连通+最短路
3180 The Cow Prom 判断有几个环， 分量中元素大于1的个数
3114 Countries in War 强连通+最短路
3592 Instantaneous Transference 强连通分量+最长路
1904 King's Quest 强连通+并查集

双连通：
3694 Network 边双连通 (同hdu2460)
3177 Redundant Paths 构造边双连通
3352 Road Construction 构造边双连通
2942 Knights of the Round Table (点双连通经典题)
1515 Street Directions (无向图改有向图)
1438 One-way Traffic (混合图改有向图)

LCA:
1330 Nearest Common Ancestors
1470 Closest Common Ancestors
1986 Distance Queries
3417 Network
3728 The merchant LCA+并查集,更新询问
2763 Housewife Wind LCA+树状数组
============================以下是2-SAT系列============================
【HDU】
3062 Party
1824 Let's go home
3622 Bomb Game
3715 Go Deeper
1815 Building roads
2723 Get Luffy Out
1816 Get Luffy Out *
1814 Peaceful Commission
4115 Eliminate the Conflict

【POJ】
2296 Map Labeler
2723 Get Luffy Out
2749 Building roads
3207 Ikki's Story IV - Panda's Trick
3648 Wedding
3678 Katu Puzzle
3683 Priest John's Busiest Day
3905 Perfect Election
============================以下是欧拉回路系列============================
【HDU】
1878 欧拉回路 判断
3018 Ant Trip 一笔画问题
1116
2894 兹鼓欧拉回路
1956
3472 混合欧拉

【POJ】
2513 欧拉路
1041 John's trip 欧拉回路
1386 Play on Words 单词接龙
2230 Watchcow 欧拉回路
2513 Colored Sticks 无向图欧拉路
2337 Catenyms 欧拉路径
1392 Ouroboros Snake 兹鼓欧拉回路
1780 code
1637 混合欧拉

【zoj】
1992
============================以下是拓扑排序系列============================
【HDU】
1285 确定比赛名次
2094 产生冠军
2647 Reward
3342 Legal or Not
1811 Rank of Tetris 拓扑+并查集
3231 三维拓扑

【POJ】
1094 Sorting It All Out Floyd+拓扑
2367 Genealogical tree
3660 Cow Contest
3687 Labeling Balls 神奇的拓扑
1128 Frame Stacking DFS版拓扑
1270 Following Orders 拓扑+回溯
1420 Spreadsheet 模拟拓扑
2762 Going from u to v or from v to u? 强连通+拓扑
3553 Task schedule
============================以下是竞赛图系列============================
竞赛图下的哈密顿问题

Strange Country II ZOJ-3332
Task Sequences POJ-1776
The book SGU-122
Tour Route POJ-3780
Tour Route HDOJ-3414