题目链接 题意 给你一张无向图，求出有多少对点对（x, y）满足从点x到点y的所有路径必同时经过点a和点b 分析 单点 首先考虑假如点a和点b是同一个点的情况 我从任意的一点出发，把所有与点a/b相连的路视为不存在，通过bfs遍历所有可能到达的点。那么这些点之间可以满足不经过点a/b能联通。反之，如果能将其他所有的点均进行bfs，组成类似并查集的数据结构，那么我可以很快得到，所有非同一集合内的点之…
题目链接 题意 给你一张无向图，求出有多少对点对（x, y）满足从点x到点y的所有路径必同时经过点a和点b 分析 单点 首先考虑假如点a和点b是同一个点的情况 我从任意的一点出发，把所有与点a/b相连的路视为不存在，通过bfs遍历所有可能到达的点。那么这些点之间可以满足不经过点a/b能联通。反之，如果能将其他所有的点均进行bfs，组成类似并查集的数据结构，那么我可以很快得到，所有非同一集合内的点之…
讨论
登录后参与讨论
还没有评论，来说第一句吧。