双连通分量

Tarjan 算法

每个点维护 dfs 和 low 两个标记

dfs时遇到每个点，有3种情况

  1. 从未被访问过 !dfn[y]
    tarjan(y);
    low[x] = min(low[x], low[y])
  2. 已经被访问，还未出栈 v[y]
    low[x] = min(low[x], dfn[y])
  3. 已经被访问，已经出栈
    忽略

对于每个点，枚举所有出边之后
如果 dfn == low
那么当前子树是一个强连通分量

P2746 [USACO5.3]校园网Network of Schools
第一问 入度为0的连通分量的个数
第二问 特判所有点在同一个连通分量中
答案是 max(入度为0的连通分量的个数, 出度为0的连通分量的个数)

构造方法
所有点在同一个连通分量中
只有1个连通分量入度为0并且只有1个连通分量出度为0，加一条边形成一个环

多个入度为0，多个出度为0
任选一个出度为0点，连向某个入度为0的点，这个入度为0的点必须可以到达其他出度为0的点。

双连通分量

割边
https://www.luogu.com.cn/problem/T103489

割点
从根节点 DFS

  1. 如果自己是根节点，自己有多于1个孩子，那么自己是割点。
  2. 如果自己不是根节点，如果存在一个孩子 low[孩子] >= dfn[自己] 那么自己是割点
  1. 双连通分量
≡