给定一个m条边的无向图 q次询问，每次询问两个点之间有多少条边
答案:1 悬赏:60
解决时间 2021-02-27 20:08
- 提问者网友：niaiwoma
- 2021-02-27 10:48
给定一个m条边的无向图 q次询问，每次询问两个点之间有多少条边
最佳答案
- 二级知识专家网友：怙棘
- 2021-02-27 11:42
看到这个题目, 您应该会想到这样的问题: 加边操作的同时询问是否连通吧, 就是并查集. 于是最先就应该考虑能不能把这个问题化归成前面说的基础问题.
既然加边变成了删边, 就可以猜想很有可能要把这个问题的过程倒过来想.
于是我们可以从没有边开始, 一条条地加边, 实际上也就是对所有点做并查集的合并操作.
那么加边的顺序呢? 显然是先加完所有没有删过的边, 然后按照从下到上的顺序依次加上题目中"删除"的边. 在中途如果有询问, 随时处理即可. (也就是说把输入倒过来读)
这样您应该会做了吧. 我只是这么想, 并没有很严谨地试过. 您再思考一下, 自己写程序吧.
既然加边变成了删边, 就可以猜想很有可能要把这个问题的过程倒过来想.
于是我们可以从没有边开始, 一条条地加边, 实际上也就是对所有点做并查集的合并操作.
那么加边的顺序呢? 显然是先加完所有没有删过的边, 然后按照从下到上的顺序依次加上题目中"删除"的边. 在中途如果有询问, 随时处理即可. (也就是说把输入倒过来读)
这样您应该会做了吧. 我只是这么想, 并没有很严谨地试过. 您再思考一下, 自己写程序吧.
我要举报
如以上问答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！
大家都在看
推荐资讯
| • 手机登qq时，显示手机磁盘不足，清理后重新登 |
| • 刺客的套装怎么选啊？ |