reward
- wrecking ball
- we can't stop
- 宿命论
算法专题
- 强连通分量《5》【√】【√】
- 倍增《3》
待啃
https://blog.csdn.net/qq_34131212/article/details/78043679 《1》
牛客练习赛27 《3》
模板
康拓展开《1》lca《1》割点《1》- 最小费用最大流《3》
UVA11525 Permutation
逆康托展开
不过不知为何,a不掉……
割点和割边
割点¶
1.为根且son>=2
if(u==fa && son>=2)gd[u]=1;
2.v不能通过非u节点到达深度比u大的节点
if(u!=fa && low[v]>=dfn[u])gd[u]=1;
割边¶
和割点差不多,还叫做割桥。
对于一个无向图,如果删掉一条边后图中的连通分量数增加了,则称这条边为桥或者割边。
实现¶
和割点差不多,只要改一处:low[v]>dfn[u]就可以了,而且不需要考虑根节点的问题。
割边是和是不是根节点没关系的,原来我们求割点的时候是指点 v是不可能不经过父节点u回到祖先节点(包括父节点),所以顶点u是割点。
如果 low[v]==dfn[u]表示还可以回到父节点,如果顶点v不能回到祖先也没有另外一条回到父亲u的路,那么u->v 这条边就是割边。