Pro.ID1593 Title「离线可过」动态图连通性 Title链接http://10.20.2.8/oj/exercise/problem?problem_id=1593 AC0 Submit1 Ratio0.00% 时间&空间限制描述这是一道被离线爆虐的模板题。 你要维护一张无向简单图。你被要求加入删除一条边及查询两个点是否连通。
输入输入的第一行是两个数 N M。N ≤ 5000 , M ≤ 500000 。 接下来 M 行,每一行三个数 op x y。 op 表示操作编号。 对于数据点 1,N ≤ 200 , M ≤ 200 对于数据点 2,N = 5, M ≤ 30 对于数据点 3,N = 10, M ≤ 1000 ,其中查询的次数 ≥ 900 次。 对于数据点 4,N = 300, M ≤ 50000 对于数据点 5,N = 5000, M ≤ 200000,没有操作 1,其中约 70% 是操作 2。 对于数据点 6,N = 5000, M ≤ 200000,没有操作 1,其中约 70 是操作 0。 对于数据点 7、8,N = 100, M ≤ 500000 对于数据点 9,N = 5000, M ≤ 500000,图是一棵树,其直径 ≤ 6 。 对于数据点 10, N = 5000, M ≤ 500000,图是一棵树,其每个点度数 ≤ 4 。 P.S. 其实 9 是菊花,10 是单链,而没有放随机树的点... 输出Description 这是一道被离线爆虐的模板题。 你要维护一张无向简单图。你被要求加入删除一条边及查询两个点是否连通。
Input 输入的第一行是两个数 N M。N ≤ 5000 , M ≤ 500000 。 接下来 M 行,每一行三个数 op x y。 op 表示操作编号。 对于数据点 1,N ≤ 200 , M ≤ 200 对于数据点 2,N = 5, M ≤ 30 对于数据点 3,N = 10, M ≤ 1000 ,其中查询的次数 ≥ 900 次。 对于数据点 4,N = 300, M ≤ 50000 对于数据点 5,N = 5000, M ≤ 200000,没有操作 1,其中约 70% 是操作 2。 对于数据点 6,N = 5000, M ≤ 200000,没有操作 1,其中约 70 是操作 0。 对于数据点 7、8,N = 100, M ≤ 500000 对于数据点 9,N = 5000, M ≤ 500000,图是一棵树,其直径 ≤ 6 。 对于数据点 10, N = 5000, M ≤ 500000,图是一棵树,其每个点度数 ≤ 4 。 P.S. 其实 9 是菊花,10 是单链,而没有放随机树的点... Output 对于每一个 op=2的询问,输出一行 Y 或 N ,表示两个节点是否连通。 Sample Input Sample #1 Sample Output Sample #1 Author 样例输入Sample #1 样例输出Sample #1 提示作者 |