88pts WA 求调
查看原帖
88pts WA 求调
685964
shuqiang楼主2025/1/20 19:23
#include<iostream>
#include<vector>

using namespace std;

const int N = 1e5 + 10, M = 2e5 + 10;
int n, m, fa[N], sz[N];
vector<int> g[M], stk;

struct opt{
	int op, u, v, ans;
} a[M];

int get(int u){
	if(fa[u] == u) return u;
	return get(fa[u]);
}

void merge(int u, int v){
	u = get(u), v = get(v);
	if(u == v) {stk.push_back(114514); return;}
	if(sz[u] > sz[v]) swap(u, v);
	fa[u] = v; sz[v] += sz[u]; stk.push_back(u);
}

void back(){
	int x = stk.back(); if(x == 114514) return; 
	stk.pop_back(); sz[fa[x]] -= sz[x]; fa[x] = x;
}

void dfs(int u){
	if(a[u].op == 1) merge(a[u].u, a[u].v);
	if(a[u].op == 3){
		if(get(a[u].u) == get(a[u].v)) a[u].ans = 1;
		else a[u].ans = 0;
	}
	for(int v: g[u]){
		dfs(v);
	}
	if(a[u].op == 1) back();
}

int main(){
	cin >> n >> m;
	for(int i = 1; i <= n; i++) fa[i] = i, sz[i] = 1; a[0].op = 2;
	for(int i = 1; i <= m; i++){
		cin >> a[i].op >> a[i].u;
		if(a[i].op == 2){
			g[a[i].u].push_back(i);
		}
		else{
			cin >> a[i].v;
			g[i-1].push_back(i);
		}
	}
	dfs(0);
	for(int i = 1; i <= m; i++){
		if(a[i].op == 3) cout << a[i].ans << '\n';
	}
	return 0;
}

2025/1/20 19:23
加载中...