并查集

目录

并查集

例题：小美的朋友关系

并查集

并查集用于处理一些不交集的合并和查询问题，有两个功能：1、判断任意两个元素是否属于同一集合   2、按照要求合并不同的集合

例题：小美的朋友关系

逆向思维：将要删除的边标记出来，构建图时跳过要删除的边，倒着遍历q查询，遇到2操作，一步一步还原删除边的过程，即往图中一步一步加边。

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <algorithm>
using namespace std;

unordered_map<int, int> fa;

int find(int x) {//查找元素所在的集合
    if (fa[x] != x) fa[x] = find(fa[x]);
    return fa[x];
}

void merge(int x, int y) {//合并两个集合
    fa[find(x)] = find(y);
}

int main() {
    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<int>> op(q, vector<int>(3));
    set<pair<int, int>> g;
    set<pair<int, int>> del;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        if (u > v) swap(u, v);
        g.insert({u, v});
        fa[u] = u;//初始化，每个节点的父亲为自己
        fa[v] = v;
    }
    for (int i = 0; i < q; i++) {
        cin >> op[i][0] >> op[i][1] >> op[i][2];
        if(op[i][1]>op[i][2]) swap(op[i][1],op[i][2]); //注意在此处交换
        int u = op[i][1], v = op[i][2];
        fa[u] = u;
        fa[v] = v;
        if (op[i][0] == 1) del.insert({u, v});
    }
    for (auto [u, v] : g) {
        if (del.count({u, v})) continue;
        merge(u, v);
    }
    vector<string> res;
    for (int i = q - 1; i >= 0; i--) {
        int u = op[i][1], v = op[i][2];
        if (op[i][0] == 1 && g.count({u, v})) {
            merge(u,v);
        }
        else if (op[i][0] == 2) {
            u=find(u),v=find(v);
            if (u==v) res.push_back("Yes");
            else res.push_back("No");
        }
    }
    reverse(res.begin(), res.end());
    for (string s:res) {
        cout << s << '\n';
    }
    return 0;
}
// 64 位输出请用 printf("%lld")