欢迎来到Introzo百科
Introzo百科
【2020小米网选D Router Mesh】Tarjan问每个点属于哪一个点双连通组件
传送门
给定一个无向图，对每个节点进行查询。问题是，如果删除这个点（及其所有相关边），整个图中会有多少个连通块？
用Tarjan算法的思想来写，dfn[i]表示节点i的dfs阶，而low[i]表示从节点i dfs可以到达的dfn值最小的节点的dfn值。如果u是当前节点，v是u的未访问子节点，如果对v完成dfs后，得到low[v] <= dfn[u]，那么就意味着从u的父节点，经过u，我们可以在到达v时，如果删除节点u，则无法到达节点v。这相当于删除节点u。 u 和节点 v 的父节点会被分成两个连通的块，即两部分不能互相到达。因此，你只需要计算你有多少个节点。子节点v满足Fuzzy [v] <= dfn [u]。当然，u的父节点也是子节点，所以需要+1来包含父节点。但每次dfs的起点都没有父节点，所以不需要+1。
总结一下，删除节点u有什么影响呢？假设删除节点 u 将添加 ans[u] 连接块。该无向图最初包含 m 个连通块。该节点原本属于 1 个连通块。删除后，会添加 ans[u] 个连通块。 block，那么删除该节点后的连通块数应为m-1+ans[u]。
#包括
#包括
#包括
#包括
#包括
#包括
#包括
相关文章
- 10-05 元宵
- 10-05 三论宗
- 10-05 直（538～597）
- 10-05 杲杳
- 10-05 海明威著作（海明威著作的中心主题）
- 10-05 藏族女歌手（藏族女歌手中白）
- 10-05 孤独指数十级（孤独指数十级排序）
- 10-05 快手kk（快手Kk的纹身）
- 10-05 手机备份在哪里（哪里找手机备份）
- 10-05 净小白（净小白是什么）
- 10-05 老虎有多重（成年老虎有多重）
- 10-05 东亚灰狼（中国田园犬为何被禁）
- 10-05 假货（假货怎么发音以及什么意思）
- 10-05 线性主部分（微分就是函数增量的线性主部分）
- 10-05 生豆芽技术（生豆芽如何种植）
- 10-05 4TB SN850X 售价 480 美元
- 10-05 随着智能手机内存的增加，消费存储市场下降 4%
- 10-05 PIBOT的机器人可以完美驾驶飞机
- 10-05 Ilysia VR 团队汲取教训并致力于提高透明度
- 10-05 《Evercore Heroes》结束内测，进入开
- 最近发表