集合问题——并查集

• 问题引入
• 算法原理
• 参考代码

问题引入

给出n个人的m个关系，表示给出的两个人都是朋友关系，之后进行k次询问，要求判断给出的两人是否是朋友关系，朋友的朋友也是朋友

算法原理

简单来说就是对集合的合并进行一个处理，使得是朋友的一群人用一个共同的朋友记录，这样在查询的时候就可以通过每个人记录的朋友判断是否是朋友。

参考代码

struct DSU {
    int fa[100007];
    //并查集，支持查找、合并、计数操作（最后剩余多少集合）
    map<int, int> root;
    DSU(int n) {for(int i=1; i<=n; i++) fa[i] = i;}
    int find(int x) {
        if(fa[x] == x) return x;
        return fa[x] = find(fa[x]);
    }
    void us(int x, int y) {
        fa[find(x)] = find(y);
    }
};