14238: 【原4238】Number Games

题目描述

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

题目内容

给出\(n\)个数，分别为\(1\cdots n\)，起始状态他们互相独立。现在需要支持以下3个操作。
1 X Y ：将两个数连接起来；
2 A B：询问A、B两个数是否连通，如果是输出YES，反之输出NO；
3 A：从图上隐藏A这个数。
注意：隐藏数只会影响查询，不影响连通性。

输入格式

第一行两个整数\(n, m\)，分别代表\(n\)个数和\(m\)条操作。
而后的\(m\)行分别为上述说到的三个操作。

输出格式

对于每个操作2，输出1行结果，为大写的YES或NO。

样例输入

样例输出

YES
NO

数据规模

对于30%的数据，\(1 \leq m, n \leq 2\times 500\)。对于100%的数据，\(1 \leq m, n \leq 2\times 10^5\)。

q4x3's solution

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

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

void read(int &x){
    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() {
    read(n); read(m);
    init();
    for(int i = 0;i < m;++ i) {
        read(op);
        if(op == 1) {
            read(x); read(y);
            bind(x, y);
        } else if(op == 2) {
            read(x); read(y);
            if(hide[x] | hide[y]) printf("NO\n");
            else if(find(x) != find(y)) printf("NO\n");
            else printf("YES\n");
        } else {
            read(x);
            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;
}