首页 > Router Mesh
开通博客写题解
头像 W.A.R
发表于 2020-10-25 19:13:07
【2020小米网络选拔赛D Router Mesh Tarjan求每个点属于哪几个点双连通分量】求删掉一个点后的连通块个数，对每个点进行一次询问 传送门 题意 给一个无向图，对每一个结点做一个询问，询问为，若删掉该点（及所有与其相关的连边），整个图有几个连通块？ 题解 用Tarjan算法的思路来写， 展开全文
去ta的博客 赞 (4) 回复(1) 收起
头像 昵称很长很长真是太好了
发表于 2020-10-27 00:34:54
题意：模板题，求图中每个割点能把网络分成几个点双连通分量（不是割点就输出他有几块即可）。 题解：跟POJ 的SPF很像 这题用Tarjan来求，首先我们需要统计出来具体有几个连通块。对于每个连通块，我们需要判断这个割点去掉后，这幅图会被分成几块？这个其实很简单，只需要更改一下判断这个点是否为割点即可 展开全文
去ta的博客 赞 (3) 回复(1) 收起
头像 ✎﹏𝓣𝔂𝓾
发表于 2020-10-28 21:10:41
D-Router Mesh（2020ICPC·小米 网络选拔赛第一场） 题意 给一个无向图，对每一个结点做一个询问，询问为，若删掉该点（及所有与其相关的连边），整个图有几个连通块？ 前置知识：强连通 回顾一下相关知识： dfn[x]： 中， 实际被访问的时间点。low[x]： 中， 通过无向边，可回 展开全文
去ta的博客 赞 (3) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”