Sorry, your browser cannot access this site
This page requires browser support (enable) JavaScript
Learn more >

无向图割点/桥&双连通分量

无向图图中所有边要么是树边,要么是反向边。

割点的条件

  1. 当树根有两个及以上子节点时,树根是割点。
  2. 非根节点u为割点,当且仅当该点存在一个子节点v,且v及其所有后代都没有反向边连回u的祖先。(连回u不算,此时u是割点)

用LOW[x]代表x及其后代能连回祖先最小的DFN值,那么上述条件即为u存在一个子节点v,使得LOW[v] DFN[u].

另外,若v的后代最早只能连到v自己,那么边(u,v)是桥。

一年半前为了省选学网络流之后第一次做网络流的题

首先是自己改造后的Dinic:



本站总访问量为 访客数为