并查集

并查集可以解决什么问题：
两个节点是否在一个集合，也可以将两个节点添加到一个集合中

并查集的核心思路在于，不管你是x->y，还是y->x，不管边什么方向。只要找到了他们的最根节点，并且连接起来。就相当于把两个不相连的图连接起来了，并且最妙的是这两个图连接起来后，根节点自动切换成同一个。这个数据结构真的是秒啊

使用的tips

注意一定要先初始化init()

init

并查集初始化，所有节点的根指向本身

// 并查集初始化
void init() {
    for (int i = 1; i <= n; i++)  father[i] = i;
}

join

tips: join(u,v) 不是将u和v相连，而是将它们的根相连

即 join(int u, int v) 函数里 要分别对 u 和 v 寻根之后再进行关联

// 将v->u 这条边加入并查集
void join(int u, int v) {
    u = find(u); // 寻找u的根
    v = find(v); // 寻找v的根
    if (u == v) return ; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回
    father[v] = u;
}

find

函数返回类型为 int

// 并查集里寻根的过程
int find(int u) {
    if (u == father[u]) return u; // 如果根就是自己，直接返回
    else return find(father[u]); // 如果根不是自己，就根据数组下标一层一层向下找
}

路径压缩：将非根节点的所有节点直接指向根节点 ， 减少 下次查询的路径长度

我们只需要在递归的过程中，让 father[u] 接住 递归函数 find(father[u]) 的返回结果。

因为 find 函数向上寻找根节点，father[u] 表述 u 的父节点，那么让 father[u] 直接获取 find函数 返回的根节点，这样就让节点 u 的父节点 变成根节点。

// 路径压缩后 并查集里寻根的过程
int find(int u) {
    if (u == father[u]) return u;
    else return father[u] = find(father[u]); // 路径压缩
}

isSame

// bool isSame(int u,int v){
//     return find(u) == find(v); 
// }
// 判断 u 和 v是否找到同一个根
bool isSame(int u, int v) {
    u = find(u);
    v = find(v);
    return u == v;
}

冗余连接

现给定一个拥有 n 个节点（节点编号从 1 到 n）和 n 条边的连通无向图，请找出一条可以删除的边，删除后图可以变成一棵树。

一个树要是节点数量不变，硬加一条边，那一定会出现环

并查集题目合集

判断连通图

给定一个无向图和其中的所有边，判断这个图是否所有顶点都是连通的

void join(int u,int v){
    u = find(u);
    v = find(v);
    if(u == v) return;
    f[u] = v;
    w[v] += w[u];
}


int main(){
    init();
    int x,y;
    while(cin >> n >> m){
        init();
        for(int i=1;i<=m;i++){
            cin >> x >> y;
            join(x,y);
        }
        int fa = find(1);
        if(w[fa] == n) cout << "YES" << "\n"; //所有顶点都连通，即要求n个点都连通
        else{
            cout << "NO" << "\n";
        }
    }
    
    
    return 0;
}

连通块中点的数量

void join(int u,int v){
    u = find(u);
    v = find(v);
    if(u == v) return;
    f[u] = v;
    s[v] += s[u]; //点个数相加
}

if(op == "Q2"){
    cin >> a;
    cout << s[find(a)] << "\n";
}

连通块个数

int cnt = n; 

//for循环完所得到的cnt即为连通块个数
for(int i=1;i<=n;i++){
    if(f[i] != i){
        cnt --;
    }
}


//使全省任何两个城镇间都可以实现交通，即将目前分割开的连通块连接在一起
//需要新修的路 = 连通块个数 - 1
cout << cnt-1;
return 0;