无向图的连通性
dfs 树
dfs 树上存在树边和返祖边,不存在横叉边。
割点
若一点 \(u\) 是割点,那么必定存在一个儿子,删去 \(u\) 后和他的父亲不连通。如果不存在,和 \(u\) 相连的所有点依然联通,那么连通性不变,不是割点。
若是根节点,若有至少 \(2\) 个儿子那么就是割点。
判断一个点不经过父亲回到它的祖先,分别记录 \(dfn,low\),分别表示 \(dfs\) 序,和不经过父亲走到的点的最小 \(dfn\) 序。
对于一个点 \(u\),若存在它的一个儿子 \(v\) 满足 \(low_v \le dfn_v\),那么 \(u\) 点就是割点。
void tarjan(int u){
dfn[u]=low[u]=++cnt;
for(auto v:to[u]){
if(dfn[v]!=0)low[u]=std::min(low[u],dfn[v]);
else {
tarjan(v);
low[u]=std::min(low[u],low[v]);
}
}
}
点双连通分量
点双就是割点分割出的连通块,并上相邻的割点。
可以发现一个点可能存在于多个点双中,但每个点只会出现在一个点双中。
开一个栈,tarjan
访问时把边入栈,如果找到边 \((u,v)\),\(low_v\le dfn_u\),则把栈里的边一一弹出直到 \(u\),构成点双。
也可以存点,但没法对每个点染色。
割边
割边不是返祖边。对于一条树边,如果是割边,那么删除后,上下不连通。
对于一个点,若 \(dfn_u=low_u\),那么它和其父亲间的边就是割边。
边双连通分量
开栈,tarjan
递归将点入栈,若存在点 \(u\) 使得 \(low_u\le dfn_u\),则弹出栈中的边直至点 \(u\),构成边双。
可以对点染色,缩完为一棵树。
Problem 1
\(n\) 点 \(m\) 边的无向图,求至少添加多少边使得任意两点间有两条边不相交的路径。\(n,m\le 10^6\)。
转换成边双(无割边)。
先缩边双,成一棵树,只要计算叶子节点的个数,答案就是 \(\lceil \frac{x}{2}\rceil\)。
P8867 NOIP2022 建造军营
\(n\) 座城市,\(m\) 条双向边连接,联通。
选择至少一座城市建造军营,还可以选择若干条边看守,同时在没有看守的路上会任意断一条边。
求有多少种方案满足不会有两个军营不连通。
HNOI2012 矿场搭建
POJ 2942
有向图的连通性
强连通分量
强连通分量里的点可以相互到达(有向图)。
同样 tarjan
遍历,若出现返祖边,那么就有了一环,环上的点都在一个强连通分量中,判断条件为 \(dfn_u=low_u\)。
ZJOI2007 最大半联通子图
JSOI2010 连通树
APIO2009 抢掠计划