做题网站推荐: OpenJudge VIJOS UOJ CF JOYOI CODEVS 洛谷 RQNOJ BZOJ POJ HDU

本站题目推荐: 高精度 模拟 排序 递推 贪心 递归 搜索 动态规划 数学 图论 数据结构 实名认证 卡评测举报

输入输出 变量类型 顺序结构 选择结构 循环结构 一维数组 NOIP 资源下载


问题 1476. -- 连通(并查集)

1476: 连通(并查集)

时间限制: 2 Sec  内存限制: 128 MB
提交: 113  解决: 16
[上一题][提交][讨论版][状态][下一题]

题目描述

给定一个无向图,请编写一个程序实现两种操作:
D x y 从原图中删除连接x,y节点的边。
Q x y 询问x,y节点是否连通。

输入

第一行两个数n,m(5<=n,m<=500000)分别表示顶点数和边数。
接下来m行,每行一对整数 x 和y (x,y<=n),表示x,y之间有边相连。保证没有重复的边。
接下来一行一个整数 q(q<=500000)
以下q行每行一种操作,保证不会有非法删除。

输出

按询问次序输出所有Q操作的回答,每行一个,连通的回答C,不连通的回答D。

样例输入

3 3
1 2
1 3
2 3
5
Q 1 2
D 1 2
Q 1 2
D 3 2
Q 1 2

样例输出

C
C
D

提示

由于原题测试文件很大,只放出部分数据测试,时限2秒。


《高级数据结构》习题4-4

来源:南京邮电大学 NOJ 1044

标签

[上一题][提交][讨论版][状态][下一题]