问题描述
小蓝是 H 市的市长，她正在用设计软件规划 H 市的道路建设。 小蓝可以选定两个地区，用一条双向道路将这两个地区连接。由于预算等因素的动态变化，小蓝经常需要拆除一些已经建设好的道路，同时，她希望知道对于当前的两个地区，是否存在一条由多条道路组成的路径能够连接这两个地区。
输入格式
输入的第一行包含两个正整数 n,m ，用一个空格分隔，其中 n 表示地区个数，m 表示操作次数。
接下来 m 行，每行表示一个操作。对于每一行：
- 1 xi yi 表示小蓝修建了一条连接地区 xi 与地区 yi 的双向道路。
- 2表示小蓝拆除了当前 H 市中还未被拆除的最后修建的一条道路，如果当前城市中已经不存在道路，则小蓝不会进行任何操作。
- 3 xi yi 表示小蓝希望知道地区 xi 与地区 yi 是否连通，即是否存在一条由多条道路组成的路径能够连接这两个地区。
输出格式
对于每个操作 3 输出 Yes 或 No，其中 Yes 表示连通，No 表示不连通。
样例输入 1
2 5
3 1 2
1 1 2
3 1 2
2
3 1 2
样例输出 1
No
Yes
No
样例输出 2
3 8
1 1 2
1 1 3
1 2 3
2
3 2 3
2
3 1 2
3 2 3
样例输出 2
Yes
Yes
No
评测用例规模与约定
对于 50% 的评测用例，n,m≤3000。
对于所有评测用例，1≤n,m≤300000，1≤xi,yi≤n，xi≠yi。
解题思路
问题的意思就是找两个地方之间是否可以连通，可以用并查集做。用dfs会超时，只能通过4个样例。（不了解并查集的可以看这篇文章理解什么是并查集-CSDN博客）
新建一条路就是将这两个点合并（此时两个地方连通，且根节点相同），毁掉一条最近新建的路就是撤销最近一次的合并（所以需对每次新建的路的信息进行存储，同时还要区分开哪些能合并哪些不能合并，方便后面只撤销合并）。
判断两个地方之间是否连通，其实就是找这两个点的根节点是否相同。
代码
本文用java语言实现，重要的是解题思路，想要python版的可以把代码丢给AI生成。
import java.util.Scanner;
public class Main {
public static int n;
public static int[] parent;
public static int[][] stack;
public static int[] rank;
public static int stacksize=0;
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
int m=sc.nextInt();
parent=new int[n+1];
rank=new int[n+1];
//初始化并查集
for(int i=1;i<=n;i++) {
parent[i]=i;
rank[i]=1;
}
//初始化栈，存储合并操作([x,y,fx,fy,merged,rank[fx],rank[fy])
stack=new int[m+1][7];
while(m-->0) {
int ope=sc.nextInt();
if(ope!=2) {
int v=sc.nextInt();
int u=sc.nextInt();
if(ope==1) {
union(v,u);
}
if(ope==3) {
if(find(v)==find(u)) {
System.out.println("Yes");
}else {
System.out.println("No");
}
}
}else {
if(stacksize>0) {
undoLastEdge();
}
}
}
sc.close();
}
//并查集查找操作(带路径压缩)
public static int find(int x) {
/*
* if(parent[x]!=x) { parent[x]=find(parent[x]);//路径压缩 } 不能用路径压缩，通过不了
*/
while(parent[x]!=x) {
x=parent[x];
}
return x;
}
//并查集合并操作(按秩（树的高度）合并)
public static void union(int x,int y) {
int fx=find(x);
int fy=find(y);
boolean merged=(fx!=fy);//根结点不同，可以合并
// 记录边信息到栈
stack[++stacksize] = new int[]{x, y, fx, fy, merged ? 1 : 0, rank[fx], rank[fy]};
//按秩合并：将秩小的合并到秩大的
if(merged) {
if(rank[fx]<rank[fy]) {
parent[fx]=fy;
}else {
parent[fy]=fx;
if(rank[fx]==rank[fy]) {
rank[fx]++;
}
}
}
}
public static void undoLastEdge() {
int[] op=stack[stacksize--];
int fx=op[2],fy=op[3];
boolean merged=(op[4]==1);//判断是否是合并过的
if(merged) {
// 恢复合并前的父节点和秩
parent[fx] = fx;
parent[fy] = fy;
rank[fx] = op[5];
rank[fy] = op[6];
}
}