首页 > Network
开通博客写题解
头像 __故人__
发表于 2020-11-20 15:13:39
分析 考虑求出边双连通分量，那么题目其实就是在问，有多少个桥。那么由于边双缩点之后，整个图变为树。那么树的边数就是答案。考虑新加一条边之后的贡献。那么就是树上距离，在将这个链上的权值变为 。这个考虑树链剖分或者 维护，写完才发现，好像直接并查集时间复杂度好像还要更优。这里采用了 实现，时间总复 展开全文
去ta的博客 赞 (8) 回复(0) 收起
头像 DeNeRATe
发表于 2020-11-28 17:23:26
分析 首先我们先求出整张图最开始的边双连通分量然后考虑之后加边操作对答案的贡献我们发现，当加入一条从双连通块x到y的边后树上（边双连通分量构成的树）从x到y路径上的所有边都不再对答案有贡献了所以我们主要的任务就是如何剪掉这部分的贡献 本题提供3种做法： 算法一 由于数据范围所以我们直接暴力跳即可时间 展开全文
去ta的博客 赞 (7) 回复(0) 收起
头像 Dear㉿You
发表于 2020-11-23 16:08:43
Network 题意 给定一张个点,条边的无向连通图，然后执行次操作,每次向图中添加一条边，并且询问图上桥的数量 前置芝士 无向图的割点和桥 给定无向连通图1.若对于 ,从图中删去节点以及所有关联边之后，分裂为两个或两个不相连的子图，则称为的割点2.若对于 ,从图中删去边之后，分裂为两个不 展开全文
去ta的博客 赞 (5) 回复(1) 收起
头像 林思艺
发表于 2020-11-20 21:03:43
题意 一个无向图可以有重边，下面 个操作，每次在两个点间连接一条有向边，每次连接后整个无向图还剩下多少桥（注意是要考虑之前连了的边，每次回答是在上一次的基础之上） 分析 求出桥来之后缩点，缩点运用并查集实现，每一个点组用父亲节点代表。emm，好像就这样。 PS: 虽说楼上大佬说并查集实现更快，但我 展开全文
去ta的博客 赞 (5) 回复(1) 收起
头像 royzhu
发表于 2020-11-25 13:24:47
Network题解 题意： 给一张n个点m条边的无向连通图，然后是q次连边操作（n<=1e5,m<=2e5,q<=1e3） 边双连通图：一张无向连通图不存在桥。边双连通分量：无向连通图的极大边双连通子图。 思路 首先是把桥都给找出来。然后思考怎样连两点会对答案有影响。如果两点都 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 平凡的小白
发表于 2020-11-29 16:47:28
我开始是想每加一条边就跑一次图，找割边的数量，特判了一下之间有两条边的情况，但还是没过，只过了：code 思路：先求出图中的割边（桥）的数量（可能有重边，输入时的重边应该算是一条边），并将同一个边双连通分量缩成一个点集，用去维护（并查集），并保留每个点的父结点。接下来就考虑缩点后形成的树，为边，边双 展开全文
去ta的博客 赞 (1) 回复(1) 收起
查看本题
查看本题讨论

相关比赛

等你来战

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

扫描二维码，进入QQ群

扫码关注“比赛自动姬”