【小码匠自习室】12月份划重点：并查集

#include <bits/stdc++.h>

using namespace std;
#define endl '\n';

vector<int> fa(10005); //先初始化一个大数组

int Find(int a) {
    if (a != fa[a]) { //如果a的父节点不是本身，就往前找到其祖宗节点
        fa[a] = Find(fa[a]); //往回返的时候把路上遍历过的所有节点更新为祖宗节点
    }
    return fa[a];
}

void Union(int x, int y) {
    int a = Find(x);
    int b = Find(y); //找到两个数的祖宗节点
    if (a != b) {
        fa[b] = a; //合并时只改其祖宗节点
    }
}

void find_union(int x, int y) { //需要输出值时使用的，和上面原理一样
    int a = Find(x);
    int b = Find(y);
    if (a == b) {
        cout << "Y" << endl;
    } else {
        cout << "N" << endl;
    }
}

void best_coder() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        fa[i] = i; //要记得现将每个节点的祖宗节点更新为本身
    }
    for (int i = 0; i < m; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        if (a == 1) { //根据题目要求调用不同的函数就OK啦
            Union(b, c);
        } else {
            find_union(b, c);
        }
    }
}

void happy_coder() {
}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    // 返回
    return 0;
}

#include <bits/stdc++.h>

using namespace std;
#define endl '\n';

struct UF {
    vector<int> fa;

    UF(int n) : {
        fa(n) {}
    }
    
    void initialize (int n) {
        for (int i = 1; i <= n; ++i) {
            fa[i] = i; //要记得先将每个节点的祖宗节点更新为本身
        }
    }

    int Find(int a) {
        if (a != fa[a]) { //如果a的父节点不是本身，就往前找到其祖宗节点
            fa[a] = Find(fa[a]); //往回返的时候把路上遍历过的所有节点更新为祖宗节点
        }
        return fa[a];
    }

    void Union(int x, int y) {
        int a = Find(x);
        int b = Find(y); //找到两个数的祖宗节点
        if (a != b) {
            fa[b] = a; //合并时只改其祖宗节点
        }
    }

    bool is_same(int x, int y) { //判断两个数在不在一个集合里
        return Find(x) == Find(y);
    }
};

void best_coder() {
    int n, m;
    cin >> n >> m;
    UF uf(n);
    uf.initialize(n);
    for (int i = 0; i < m; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        if (a == 1) { //根据题目要求调用不同的函数就OK啦
            uf.Union(b, c);
        } else {
            if (uf.is_same(b, c)) {
                cout << "Y" << endl;
            } else {
                cout << "N" << endl;
            }
        }
    }
}

void happy_coder() {
}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    // 返回
    return 0;
}