# 14238: 【原4238】Number Games

### 题目描述

author: Pikachu 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4238

## 题目内容

1 X Y ：将两个数连接起来；
2 A B：询问A、B两个数是否连通，如果是输出YES，反之输出NO；
3 A：从图上隐藏A这个数。

## 样例输入

3 5
1 2 3
1 1 2
3 2
2 1 3
2 2 3


## 样例输出

YES
NO


## q4x3's solution

/**
* 并查集 + 路径压缩模板题
**/
#include <iostream>
#include <cstdio>

const int MAXN = 2e5 + 233;
int fa[MAXN], n, m, op, x, y;
bool hide[MAXN];

x = 0;
char ch;
while (ch = getchar(), (ch < '0' || ch > '9'));
x = ch - '0';
while(ch = getchar(), ch >= '0' && ch <= '9') x = 10 * x + ch - '0';
}

int init() {
for(int i = 1;i <= n;++ i)
fa[i] = i;
}

int find(int x) {
int son = x;
// 路径压缩迭代写法
// if(fa[x] == x) return x;
// else return fa[x] = find(fa[x]);
// 路径压缩循环写法
while(fa[x] != x) {
x = fa[x];
}
while(son != x) {
int tmp = fa[son];
fa[son] = x;
son = tmp;
}
return x;
}

int bind(int x, int y) {
fa[find(x)] = find(y);
}

int main() {
init();
for(int i = 0;i < m;++ i) {
if(op == 1) {
bind(x, y);
} else if(op == 2) {
if(hide[x] | hide[y]) printf("NO\n");
else if(find(x) != find(y)) printf("NO\n");
else printf("YES\n");
} else {
hide[x] = 1;
}
}
}


## victrid's solution

#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

int father[100005] = {0};
bool del[100005]   = {false};

int anc(int x) { return father[x] == x ? x : father[x] = anc(father[x]); }

int main() {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
father[i] = i;
int op, x, y;
while (m--) {
scanf("%d", &op);
switch (op) {
case 1:
scanf("%d%d", &x, &y);
father[anc(x)] = anc(y);
break;
case 2:
scanf("%d%d", &x, &y);
if (del[x] || del[y])
printf("NO\n");
else
printf(anc(x) == anc(y) ? "YES\n" : "NO\n");
break;
case 3:
scanf("%d", &x);
del[x] = true;
break;
}
}
return 0;
}