何曾有丶飞的梦想

图论

CCF(6) C语言(1) git(1) Java(3) Linux(3) PAT(7) POJ刷题记录(21) python(1) 分层图(1) 区间操作(2) 可持续化数据结构(1) 数学(1) 最近公共祖先(1) 汇编(1) 算法(6) 英语(2) 蓝桥杯(1) 计算机组成原理(1) 计算机网络(1) 题解(1)

/ 注册

全部文章 / 图论（共2篇）

二分图

结论不存在奇数环染色法不存在矛盾匈牙利最大匹配数 = 最小点覆盖 = 总点数- 最大独立集 = 总点数- 最小路径覆盖最小路径重复点覆盖 = 传递闭包+ 最小路径覆盖最小路径覆盖做法：拆点思想

2020-07-21

0 445

强连通分量（有向图无向图）

有向图双连通分量图：max(p,q); p 起点 q 终点无向图边双连通分量判定： dfn[u] < low[to] 边双连通分量图: (cnt + 1) / 2; 点双连通分量判定：1：dfn[u] <= low[y]2: (1) u 不是根...

tarjan

2020-07-21

0 645