一个离线维护加边后边双联通的玩意。

图不保证联通。

#include<bits/stdc++.h>
#define Maxn 2000005 
using namespace std;
struct egde {
	int u,v,w; 
	bool operator<(const egde&is) 
	const {return w > is.w;} 
} e[Maxn];
struct Query {
	int id,u,v;
} Q[Maxn];
int find(int x,int *f) {
	return f[x] == x?x:f[x] = find(f[x],f);
}
int f[Maxn],g[Maxn];
vector<int> q[Maxn];
int dep[Maxn],F[Maxn];
void dfs(int x,int fa) {
	F[x] = fa;
	dep[x] = dep[fa] + 1;
	for(int u:q[x]) 
	if(u != fa) dfs(u,x);
}
bool ans[Maxn];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,m,t,tid;
	cin>>n>>m>>t>>tid;
	for(int i=1;i<=m;i++)
		cin>>e[i].u>>e[i].v,e[i].w = t+1;
	for(int i=1;i<=t;i++) {
		cin>>Q[i].id;
		if(Q[i].id == 1)
			cin>>Q[i].u,e[Q[i].u].w = i;
		else cin>>Q[i].u>>Q[i].v;
	}
	for(int i=1;i<=n;i++)
		f[i] = g[i] = i;
	sort(e+1,e+1+m);
	for(int i=1;i<=m;i++) {
		int u = e[i].u,v = e[i].v;
		int fu = find(u,f),fv = find(v,f);
		if(fu != fv) {
			q[u].push_back(v);
			q[v].push_back(u);
			f[fu] = fv;
			e[i].w = -1;
		}
	}
	for(int i=1;i<=n;i++)
		if(!dep[i])dfs(i,i);
	int p = t;
	while(Q[p].id == 1)p --;
	for(int i=1;i<=m;i++) {
		if(e[i].w == -1)continue;
		while(p > 0&&p > e[i].w) {
			if(find(Q[p].u,g) == find(Q[p].v,g))
				ans[p] = true; p --;
			while(p > 0&&Q[p].id == 1)p --;
		}
		int u = find(e[i].u,g),v = find(e[i].v,g),opt = u;
		while(u != v) {
			if(dep[u] > dep[v])swap(u,v);
			g[v] = opt;
			v = find(F[v],g);
		} F[opt] = F[u],g[u] = opt;
	}
	while(p > 0) {
		if(find(Q[p].u,g) == find(Q[p].v,g))
			ans[p] = true; p --;
		while(p > 0&&Q[p].id == 1)p --;
	}
	for(int i=1;i<=t;i++)
		if(ans[i])cout<<"YES\n";
		else if(Q[i].id == 2)
			cout<<"NO\n";
	return 0;
 }