ACM:删边后询问连通性

答案:2 悬赏:10 手机版

解决时间 2021-04-02 07:31

提问者网友：玫瑰园
2021-04-01 10:26

ACM:删边后询问连通性

最佳答案

五星知识达人网友：妄饮晩冬酒
2021-04-01 10:53

看到这个题目, 您应该会想到这样的问题: 加边操作的同时询问是否连通吧, 就是并查集. 于是最先就应该考虑能不能把这个问题化归成前面说的基础问题.
既然加边变成了删边, 就可以猜想很有可能要把这个问题的过程倒过来想.
于是我们可以从没有边开始, 一条条地加边, 实际上也就是对所有点做并查集的合并操作.
那么加边的顺序呢? 显然是先加完所有没有删过的边, 然后按照从下到上的顺序依次加上题目中"删除"的边. 在中途如果有询问, 随时处理即可. (也就是说把输入倒过来读)
这样您应该会做了吧. 我只是这么想, 并没有很严谨地试过. 您再思考一下, 自己写程序吧.

全部回答

1楼网友：归鹤鸣
2021-04-01 11:55

用动态树维护一个层次图
单次操作log^2 n
可以加边，可以减边，且是动态的

我要举报

如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！