国外网站建设的研究现状,网店美工培训教程,wordpress哪个主题,北京科技公司割点
定义#xff1a;
若一个点在图中被去掉后#xff0c;图的连通块个数增加#xff0c;那么这个点就被称为“割点”。如下图所示红点。 定义说白了就是若去掉一个点#xff0c;图被“断开”的点称为割点。
朴素算法#xff1a;
枚举每个点 u。遍历图#xff0c;如果…割点
定义
若一个点在图中被去掉后图的连通块个数增加那么这个点就被称为“割点”。如下图所示红点。 定义说白了就是若去掉一个点图被“断开”的点称为割点。
朴素算法
枚举每个点 u。遍历图如果有一个点或多个点遍历不到遍历期间不能经过点 u那么 u 就是割点。
时间复杂度 O ( N 2 ) O(N^2) O(N2)。
可作为对拍暴力程序。
正解Tarjan
定义一些东西
时间戳dfs 时表示每个点被遍历到的“时间”可用一个不断增加的变量实现。记为 d f n dfn dfn。搜索树dfs 时由遍历到的边组成的树由于有打标记所以不会重复访问。追溯值以 u 为根的子树中所有不经过 u 能够到达的节点的时间戳的最小值。记为 l o w low low。
关于追溯值
结合张图来理解 设红边为搜索树的边则 3 3 3 号点因为有蓝色的边不经过他的父亲 2 2 2 号点直接到达了 1 1 1 号点所以 l o w 3 d f n 1 low_3dfn_1 low3dfn1。
回归 Tarjan
有一个重要的概念
一个点 u 如果是割点那么它的子树中的一些节点 v 的 l o w v low_v lowv 是大等于 d f n u dfn_u dfnu 的因为它到不了上面上面的意思是搜索树中比 u 更早遍历到的点集。
显然 l o w u low_u lowu 表示假设断开点 u 孩子们还能遍历到的最早时间戳。
若 l o w v ≥ d f n u low_v\ge dfn_u lowv≥dfnu v 是 u 的孩子即 v 回不到 u 前那么就表示 u 是割点。
有 s s s 个这样的 v 就代表断开 u 可以把原先的连通图变成 s 1 s1 s1 个连通块u 上方也是一个。
遍历路上
对于每个点 u遍历到的儿子 v 有两种可能 d f n v 0 dfn_v0 dfnv0
说明 v 是新加入搜索树中的节点那么就先递归下去用 l o w v low_v lowv 更新 l o w u low_u lowu。
即 l o w u m i n ( l o w u , l o w v ) low_umin(low_u,low_v) lowumin(lowu,lowv)。 d f n v ≠ 0 dfn_v\neq 0 dfnv0
说明 v 曾经
被遍历过是搜索树上 u 的祖先那么用 d f n v dfn_v dfnv 更新 l o w u low_u lowu。
即 l o w u m i n ( l o w u , d f n v ) low_umin(low_u,dfn_v) lowumin(lowu,dfnv)。
然而上述办法还是有 bug。想想在哪呢
发现 bug
假设我们搜索树从 1 1 1 号点开始遍历给张图你就懂。 如图。
因为我们是从 1 1 1 号点开始遍历的 1 1 1 号点是搜索树的根它哪来的祖先能让孩子们去更新追溯值啊
而图中的 1 1 1 号点又显然不是割点。
咋办呢
解决 bug
特判呗。反正根只有一个。
这时候我们得思考什么样的情况下根是割点
反正追溯值做不了了。
那么看看朴素的图吧。 图中 1 1 1 号点就是割点。
为啥嘞
答因为把它删了后有两个连通块。
正解。
我们记录一下如果它在搜索树上的儿子不止一个那么它就是割点。
就这么简单
就这么简单。
这时候不知道有没有同学有个疑惑和我初学时一样的如图 红色的是搜索树边。
图中 1 1 1 不是割点啊但它在树上还真有两个孩子啊
如果您一开始没看出来哪儿错了就点个赞再走吧。
注意到边 3 → 2 3\rightarrow 2 3→2 和 1 → 2 1\rightarrow 2 1→2。
当我们遍历到点 3 3 3 的时候它就会顺带把 2 2 2 号点先遍历了。先遍历到 2 2 2 再遍历 3 3 3 同理。
所以说搜索树应该为 或 OK下班看题。
洛谷 P3388 【模板】割点割顶。
题意很简略了。就是看看实现。
#includebits/stdc.h
using namespace std;
const int N2e45,M1e55;
int n,m,ehead[N],cnt_e,low[N],dfn[N],idx,rt,cntans;
bool ans[N];//是否为割点
struct E{int to,pre;
}e[M1];
void adde(int from,int to)
{e[cnt_e].toto;e[cnt_e].preehead[from];ehead[from]cnt_e;return;
}
void dfs(int u)
{low[u]dfn[u]idx;int chtree0;//如果是根的话它的孩子个数for(int iehead[u];i;ie[i].pre){int ve[i].to;if(!dfn[v])//不在搜索树上{dfs(v);low[u]min(low[u],low[v]);if(rtu)chtree;if(low[v]dfn[u]rt!u(!ans[u]))//注意 (!ans[u])。搞不好会重复算 cntans{cntans;ans[u]1;}}else//返祖边low[u]min(low[u],dfn[v]);}if(urtchtree1(!ans[u])){cntans;ans[u]1;}return;
}
int main(){ios::sync_with_stdio(0);cinnm;for(int i1,u,v;im;i){cinuv;adde(u,v);adde(v,u);}for(int i1;in;i)//图不保证联通{if(!dfn[i]){rti;dfs(i);}}coutcntans\n;for(int i1;in;i)if(ans[i])couti ;cout\n;return 0;
}闲话时间
讲个好玩的这篇文章是我晚上十一点左右写的但是 我来自报家门了。
正题。
Tarjan 算法不光能解决割点的问题改一改还能当作强连通分量和割边又称桥和双连通分量等等。
说到强连通分量推销一下我的学习笔记不过分吧 qwq。
完结撒花。
