首页 > 图论
开通博客写题解
头像 Zvelig1205
发表于 2025-12-11 20:47:08
并查集板子题。 对于并查集而言，很难进行删边操作，因此考虑将删边反过来，改为符合题意就加边。 由题意，同在 中的点不能相连，所以可以在并查集的合并过程中手动保持让 中的点作为并查集的根（同一个集合中最多有一个 中的点）。然后连边时，若两边的点（根）均为 中的点，则不连接，计入答案；否则连边， 展开全文
去ta的博客 赞 (4) 回复(2) 收起
头像 Ldh1315109
发表于 2026-01-07 06:15:19
思路： 任选一个中的点做为树的根节点，对于所有其他的在中的节点，我们只需要选择连接该节点与其父节点的边，就可以满足题目要求。 代码： def solve(testcase): n, m = MI() adj = [[] for _ in range(n)] edge 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

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

扫描二维码，进入QQ群

扫码关注“比赛自动姬”