割点和割边
在无向图中,所有能互通的点组成了一个“连通分量”。在一个连通分量中有一些关键的点,如果删除它,会把这个连通分量分成两个或更多,这种点称为割点(cut vertex)。
在一个连通分量中,如果删除一条边,把这个连通分量分成两个,这个边称为割边(cut eddge,又称为桥,bridge)。
深搜优先生成树
- T 的根节点 s 是割点,当且仅当 s 有两个或更多的子结点。
- T 的非根节点 u 是割点,当且仅当 u 存在一个子结点 v,v 及其后代都没有回退边连回 u 的祖先。
// 割点 vector<int> g[maxn]; int dfn[maxn], low[maxn], cnt; // 遍历顺序、祖先 int vis[maxn], num; // 标记割点 void dfs(int x, int fa, int son = 0) { dfn[x] = low[x] = ++ cnt; for(auto to: g[x]) { if (!dfn[to]) { dfs(to, x); low[x] = min(low[to], low[x]); if (x == fa) vis[x] = ++son > 1 ? 1 : 0; // 判断根结点是否为割点 else if (low[to] >= dfn[x]) vis[x] = 1; // 判断非根结点是否为割点 // 判断割边,把low[to] >= dfn[x] 改为 low[to] > dfn[x] 即可 } else if (to != fa) { low[x] = min(dfn[to], low[x]); } } if (vis[x]) num ++; // 统计割点个数 } void tarjin(int n) { // 无向连通图求割点 cnt = num = 0; for(int i = 1; i <= n; ++ i) { dfn[i] = low[i] = vis[i] = 0; } for(int i = 1; i <= n; ++ i) { if (!dfn[i]) dfs(i, i); } for(int i = 1; i <= n; ++ i) g[i].clear(); }
// 割边 vector<int> g[maxn]; int dfn[maxn], low[maxn], cnt; vector<pair<int,int> > bridge; // 存储割边 void dfs(int x, int fa, int k = 0) { dfn[x] = low[x] = ++cnt; for(auto to: g[x]) { if (to == fa && ++k == 1) continue; // 判重边 if (!dfn[to]) { dfs(to, x); low[x] = min(low[to], low[x]); if (low[to] > dfn[x]) { bridge.push_back(make_pair(min(x,to), max(x,to))); // 存储割边 } } else low[x] = min(dfn[to], low[x]); } } void tarjin(int n) { cnt = 0; L.clear(); for(int i = 1; i <= n; ++ i) { dfn[i] = low[i] = 0; } for(int i = 1; i <= n; ++ i) { if (!dfn[i]) dfs(i, i); } for(int i = 1; i <= n; ++ i) g[i].clear(); }
双连通分量
在一个连通图中选任意两点,如果它们之间至少存在两条“点不重复”的路径,称为点双连通。一个图中的点双连通极大子图称为“点双连通分量”(block,或者 2-connected component)。点双连通分量是一个“可靠”的图,去掉任何一个点,其他点仍然是连通的。也就是说,点双连通分量中没有割点。
类似地有“边双连通分量”,如果任意两点之间至少存在两条“边不重复”的路径,称为“边双连通”。在边双连通图中去掉任意一条边,图任然是连通的。也就是说,边双连通图中没有割边。
边双连通分量
vector<int> g[maxn]; int dfn[maxn], low[maxn], cnt; int bcc[maxn], tot; // 边双连通分量 int sta[maxn], top; int bridge[maxn], pre[maxn]; // 标记割边 int du[maxn]; // 缩点度数 void dfs(int x, int fa, int k = 0) { dfn[x] = low[x] = ++cnt; sta[top++] = x; for(int i = 0; i < g[x].size(); ++ i) { int to = g[x][i]; if (to == fa && ++k == 1) continue; // 判重边 if (!dfn[to]) { dfs(to, x); low[x] = min(low[to], low[x]); pre[to] = x; // 标记父节点 if (low[to] > dfn[x]) bridge[to] = 1; // 标记割边 } else low[x] = min(dfn[to], low[x]); } if (dfn[x] == low[x]) { // 弹出一个边连通分量 tot ++; while(1) { int y = sta[--top]; bcc[y] = tot; if (x == y) break; } } } void tarjin(int n) { top = cnt = tot = 0; for(int i = 1; i <= n; ++ i) { bcc[i] = dfn[i] = low[i] = 0; } for(int i = 1; i <= n; ++ i) { if (!dfn[i]) dfs(i, i); } for(int i = 1; i <= n; ++ i) { // 统计缩点度数 if (bridge[i]) { du[bcc[i]] ++; du[bcc[pre[i]] ++; } } int leaf = 0; for(int i = 1; i <= tot; ++ i) { // 统计缩点后的叶子结点 if (du[i] == 1) leaf ++; } for(int i = 1; i <= n; ++ i) { g[i].clear(); } }