首页 > 其他分享 >并查集

并查集

时间：2024-09-07 21:37:18浏览次数：8  
标签：return int 查集 father len vector find

并查集

  1. 一开始每个元素都以自己为一个集合
  2. find(i)：查找 i 所在集合的代表元素，代表元素代表了 i 所在的集合
  3. isSameSet(a, b)：判断 a、b 是否在同一个集合里
  4. union(a, b)：将 a、b 所在的两个集合合并

并查集的实现

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

int len;
// father[i] 为 i 所在集合的代表元素
vector<int> father;
// 记录代表元素所在集合的大小
vector<int> s1ze;
// 暂存 find 过程中经过的元素
stack<int> stk;

void build() {
    father.resize(len);
    s1ze.resize(len);
    for (int i = 0; i < len; ++i) {
        // 初始状态以自己为集合
        father[i] = i;
        s1ze[i] = 1;
    }
}

int find(int x) {
    while (x != father[x]) {
        // 往上找代表元素的过程中记录经过的节点
        stk.emplace(x);
        x = father[x];
    }
    // 路径压缩
    while (!empty(stk)) {
        father[stk.top()] = x;
        stk.pop();
    }
    return x;
}

bool isSameSet(int a, int b) {
    return find(a) == find(b);
}

void un1on(int a, int b) {
    // 找到元素所在集合的代表元素
    int fatherOfA = find(a);
    int fatherOfB = find(b);
    // 已经在同一个集合就返回
    if (fatherOfA == fatherOfB) return;
    // 小挂大：集合元素少的把代表元素挂在集合元素多的代表元素上
    if (s1ze[fatherOfA] > s1ze[fatherOfB]) {
        father[fatherOfB] = fatherOfA;
        s1ze[fatherOfA] += s1ze[fatherOfB];
    } else {
        father[fatherOfA] = fatherOfB;
        s1ze[fatherOfB] += s1ze[fatherOfA];
    }
}

int main() {
    int N, M;
    cin >> N >> M;
    len = N + 1;

    build();

    for (int i = 0, opt, a, b; i < M; ++i) {
        cin >> opt >> a >> b;
        if (opt == 1) {
            if (isSameSet(a, b)) {
                cout << "Yes" << endl;
            } else {
                cout << "No" << endl;
            }
        } else {
            un1on(a, b);
        }
    }
}

P3367 【模板】并查集

#include <iostream>
#include <vector>

using namespace std;

int len;
// father[i] 为 i 所在集合的代表元素
vector<int> father;

void build() {
    father.resize(len);
    // 初始状态以自己为集合
    for (int i = 0; i < len; ++i)
        father[i] = i;
}

int find(int x) {
    // 路径压缩
    if (x != father[x])
        father[x] = find(father[x]);
    return father[x];
}

bool isSameSet(int a, int b) {
    return find(a) == find(b);
}

void un1on(int a, int b) {
    // a 所在集合并入 b 所在集合
    father[find(a)] = find(b);
}

int main() {
    int N, M;
    cin >> N >> M;
    len = N + 1;

    build();

    for (int i = 0, opt, a, b; i < M; ++i) {
        cin >> opt >> a >> b;
        if (opt == 2) {
            if (isSameSet(a, b)) {
                cout << "Y" << endl;
            } else {
                cout << "N" << endl;
            }
        } else {
            un1on(a, b);
        }
    }
}

765. 情侣牵手

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    // 下标为情侣组号，组号为情侣编号/2
    vector<int> father;
    // 记录集合总数
    int sets;

    void build(int len) {
        father.resize(len);
        for (int i = 0; i < len; ++i) father[i] = i;
        sets = len;
    }

    int find(int i) {
        if (i != father[i])
            father[i] = find(father[i]);
        return father[i];
    }

    bool isSameSet(int a, int b) {
        return find(a) == find(b);
    }

    void un1on(int a, int b) {
        int fa = find(a);
        int fb = find(b);
        if (fa == fb) return;
        father[fa] = fb;
        // 集合总数减一
        sets--;
    }

    int minSwapsCouples(vector<int> &row) {
        int n = row.size();
        build(n / 2);

        // 所在的情侣组合并
        for (int i = 0; i < n; i += 2)
            un1on(row[i] / 2, row[i + 1] / 2);
        // 每个情侣组集合有 a 组，则这个集合至少需要 a - 1 次交换
        // 一共有 n / 2 个情侣组（每组两个人），总的交换次数就是 n / 2 - 集合总数
        return n / 2 - sets;
    }
};

839. 相似字符串组

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    vector<int> father;
    // 集合总数
    int sets;

    void build(int len) {
        father.resize(len);
        for (int i = 0; i < len; ++i)
            father[i] = i;
        sets = len;
    }

    int find(int i) {
        if (i != father[i])
            father[i] = find(father[i]);
        return father[i];
    }

    bool isSameSet(int a, int b) {
        return find(a) == find(b);
    }

    void un1on(int a, int b) {
        int fa = find(a);
        int fb = find(b);
        if (fa == fb) return;
        father[fa] = fb;
        sets--;
    }

    bool isSimilar(string s1, string s2) {
        int len = s1.size();
        int diff = 0;
        // 判断相同位置元素不同的地方有几个，为 0 或者 2 才是相似的异构词
        for (int i = 0; i < len && diff < 3; ++i)
            if (s1[i] != s2[i]) diff++;
        return diff == 0 || diff == 2;
    }

    int numSimilarGroups(vector<string> &strs) {
        int len = strs.size();
        build(len);

        for (int i = 0; i < len; ++i)
            for (int j = i + 1; j < len; ++j)
                // 相似就合并
                if (isSimilar(strs[i], strs[j]))
                    un1on(i, j);
        return sets;
    }
};

200. 岛屿数量

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    int rows;
    int columns;
    vector<int> father;
    int sets = 0;

    // 坐标映射为一维下标
    int getIndex(int a, int b) {
        return a * columns + b;
    }

    void build(vector<vector<char>> &grid) {
        father.resize(rows * columns + 1);
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < columns; ++j) {
                // 只对陆地初始化
                if (grid[i][j] == '1') {
                    int index = getIndex(i, j);
                    father[index] = index;
                    sets++;
                }
            }
        }
    }

    int find(int i) {
        if (i != father[i])
            father[i] = find(father[i]);
        return father[i];
    }

    bool isSameSet(int a, int b) {
        return find(a) == find(b);
    }

    void un1on(int a, int b) {
        int fa = find(a);
        int fb = find(b);
        if (fa == fb) return;
        father[fa] = fb;
        sets--;
    }

    int numIslands(vector<vector<char>> &grid) {
        rows = grid.size();
        columns = grid[0].size();

        build(grid);

        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < columns; ++j) {
                // 当前位置不是陆地就跳过，不需要和其他集合合并
                if (grid[i][j] != '1') continue;
                int index = getIndex(i, j);
                // 上方是陆地
                if (i > 0 && grid[i - 1][j] == '1')
                    un1on(index, getIndex(i - 1, j));
                // 左侧是陆地
                if (j > 0 && grid[i][j - 1] == '1')
                    un1on(index, getIndex(i, j - 1));
            }
        }
        return sets;
    }
};

// todo 洪水填充

947. 移除最多的同行或同列石头

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

class Solution {
public:

    // 记录第一次遇到的石头的编号，以行列为 key，石头编号为 value
    unordered_map<int, int> rowFirst;
    unordered_map<int, int> colFirst;
    vector<int> father;
    int sets;

    void build(int len) {
        rowFirst.clear();
        colFirst.clear();
        father.resize(len);
        for (int i = 0; i < len; ++i)
            father[i] = i;
        sets = len;
    }

    int find(int i) {
        if (i != father[i])
            father[i] = find(father[i]);
        return father[i];
    }

    void un1on(int a, int b) {
        int fa = find(a);
        int fb = find(b);
        if (fa == fb) return;
        father[fa] = fb;
        sets--;
    }

    int removeStones(vector<vector<int>> &stones) {
        // 石头数量
        int len = stones.size();
        build(len);

        for (int i = 0; i < len; ++i) {
            int row = stones[i][0];
            int col = stones[i][1];
            // 所有在行列上有关联的都合并到一起
            if (rowFirst.find(row) == rowFirst.end()) {
                // 该行第一次出现
                rowFirst[row] = i;
            } else {
                // 和之前在这行上第一次出现的石头合并到一个集合
                un1on(i, rowFirst[row]);
            }
            if (colFirst.find(col) == colFirst.end()) {
                // 该行第一次出现
                colFirst[col] = i;
            } else {
                // 和之前在这行上第一次出现的石头合并到一个集合
                un1on(i, colFirst[col]);
            }
        }
        // 最少剩 sets 个石头，最多移除 len - sets 个石头
        return len - sets;
    }
};

2092. 找出知晓秘密的所有专家

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<int> father;
    // 标记代表元素所在集合是否知道秘密
    vector<bool> secret;
    stack<int> stk;

    void build(int n, int firstPerson) {
        father.resize(n);
        secret.resize(n, false);
        for (int i = 0; i < n; ++i)
            father[i] = i;
        // 初始知道秘密的两个人
        secret[0] = true;
        secret[firstPerson] = true;
        // 并入一个集合
        father[firstPerson] = 0;
    }

    int find(int i) {
        if (i != father[i])
            father[i] = find(father[i]);
        return father[i];
    }

    void un1on(int a, int b) {
        int fa = find(a);
        int fb = find(b);
        if (fa == fb) return;
        father[fa] = fb;
        // 传递是否知道秘密
        secret[fb] = secret[fb] | secret[fa];
    }

    // 判断 i 是否知道秘密
    bool knowSecret(int i) {
        return secret[find(i)];
    }

    static bool cmp(vector<int> arr1, vector<int> arr2) {
        return arr1[2] < arr2[2];
    }

    vector<int> findAllPeople(int n, vector<vector<int>> &meetings, int firstPerson) {
        // 按照会议时间排序
        sort(begin(meetings), end(meetings), cmp);

        // 初始化
        build(n, firstPerson);

        // 会议总数
        int len = meetings.size();
        int i = 0;
        int time = meetings[0][2];
        while (i < len) {
            // 同一个时间开会的，关联到一个集合
            while (i < len && meetings[i][2] == time) {
                // 这一时间开会的所有人入栈，为后续分理出不知道秘密的人做准备
                stk.emplace(meetings[i][0]);
                stk.emplace(meetings[i][1]);
                // 相关联，并入一个集合
                un1on(meetings[i][0], meetings[i][1]);
                i++;
            }
            while (!stk.empty()) {
                // 不知道秘密人的要从相互关联却不知道秘密的集合中分离出来
                if (!knowSecret(stk.top())) father[stk.top()] = stk.top();
                stk.pop();
            }
            if (i < len) time = meetings[i][2];
        }

        vector<int> res;
        // 加入所有知道秘密的人
        for (int j = 0; j < n; ++j)
            if (knowSecret(j)) res.emplace_back(j);
        return res;
    }
};

2421. 好路径的数目

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;


class Solution {
public:
    // 集合中的最大值作为代表节点
    vector<int> father;
    // 记录顶点 i 所在集合的最大值和最大值的个数
    vector<int> cnt;

    void build(int n, vector<int> &vals) {
        father.resize(n);
        cnt.resize(n);
        for (int i = 0; i < n; ++i) {
            father[i] = i;
            cnt[i] = 1;
        }
    }

    int find(int i) {
        if (i != father[i])
            father[i] = find(father[i]);
        return father[i];
    }

    // 返回产生好路径的条数
    int un1on(int a, int b, vector<int> &vals) {
        int fa = find(a);
        int fb = find(b);
        int path = 0;
        // 更新标签信息
        if (vals[fa] == vals[fb]) {
            // 两个集合的最大值一样才会出现好路径
            path = cnt[fa] * cnt[fb];
            cnt[fb] += cnt[fa];
            father[fa] = fb;
        } else if (vals[fa] > vals[fb]) {
            father[fb] = fa;
        } else if (vals[fa] < vals[fb]) {
            father[fa] = fb;
        }
        return path;
    }

    int numberOfGoodPaths(vector<int> &vals, vector<vector<int>> &edges) {
        int res = vals.size();
        // vals[i] 表示顶点 i 的值，edges[i][0]、edges[i][1] 为边的两个顶点
        // 根据边的两个顶点的较大值进行排序
        sort(begin(edges), end(edges),
             [&vals](vector<int> v1, vector<int> v2) {
                 return max(vals[v1[0]], vals[v1[1]]) < max(vals[v2[0]], vals[v2[1]]);
             });

        build(res, vals);

        for (auto &edge: edges)
            res += un1on(edge[0], edge[1], vals);

        return res;
    }
};

928. 尽量减少恶意软件的传播 II

标签：return,int,查集,father,len,vector,find
From： https://www.cnblogs.com/sprinining/p/18402185

相关文章

  • 算法【并查集】
    并查集的使用是如下的场景1.一开始每个元素都拥有自己的集合，在自己的集合里只有这个元素自己。2.find(i)：查找i所在集合的代表元素，代表元素来代表i所在的集合。3.bool isSameSet(a,b)：判断a和b在不在一个集合里。4.voidunion(a,b)：a所在集合所有元素与b所在集合所有元素......
  • Luogu P7250 BalticOI 山峰 题解 [ 蓝 ] [ 模拟 ] [ 并查集 ] [ BFS ]
    LuoguP7250BalticOI山峰。一道大模拟，很暴力，也很难写。建议紫或蓝，标签为模拟、广度优先搜索、并查集。思路首先观察到答案取决于路线上的最低点，所以我们可以把所有点的高度丢进一个桶里，从大到小枚举，尝试更新答案。这应该是个挺经典的trick了。感性理解可以看作所有山都先......
  • 并查集
    并查集及其应用咸鱼说并查集22年加入考研大纲，到目前（25考研之前）还没有考过，可以压一手。定义并查集用于解决元素分组的相关问题，也就是对于一组元素，挑出一个来当作代表。并查集可以视作一种树状的数据结构，每个元素结点都有一个父节点（父节点可以是自己，此时这个结点为代表）。并查......
  • 学习笔记---并查集
    并查集并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题（即所谓的并、查）。比如说，我们可以用并查集来判断一个森林中有几棵树、某个节点是否属于某棵树等。(1)朴素并查集：intp[N];//存储每个点的祖宗节点//返回x的祖宗节点intfind(in......
  • 并查集
    在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内竞赛题中，其特点是看似并不复杂，但数据量极大，若用传统的线......
  • 并查集(保姆级讲解)
    文章目录什么是并查集查找合并例题代码什么是并查集并查集是一种树形的数据结构。支持两种操作**查找：**确定某个元素在那个集合**合并：**将两个集合的元素合并在一起查找1.朴素查找2.优化查找合并1.朴素合并2.优化合并因为朴素合并的时间复杂度已经......
  • 并查集扩展
    并查集扩展目录并查集扩展普通并查集例题:1.洛谷P1197星球大战2.洛谷P1955程序自动分析带权并查集例题:1.洛谷P2024食物链2.洛谷P1196银河英雄传说3.洛谷P5937ParityGame扩展域并查集例题:1.洛谷P1525关押罪犯普通并查集例题:1.洛谷P1197星球大战链接:[P1197JSOI20......
  • 并查集（路径压缩法+启发式合并法）
    我们从一道例题看起：洛谷P1551亲戚。问题很简单，给出一个亲戚关系图，规定\(x\)和\(y\)是亲戚，\(y\)和\(z\)是亲戚，那么\(x\)和\(z\)也是亲戚，那么\(x\)的亲戚都是\(y\)的亲戚，\(y\)的亲戚也都是\(x\)的亲戚，再给定\(P_i\)和\(P_j\)，询问他们是否是亲戚，输出Yes或......
  • 并查集
    并查集(递归写法)#include<bits/stdc++.h>usingnamespacestd;constintX=10010;intf[X];intn,m; //初始化voidinit(){ for(inti=0;i<X;i++){ f[i]=i; }}//查找上级是谁intfind(intx){ if(x!=f[x]){ returnf[x]=find(f[x]);//路径......
  • 【知识】并查集的单点删除 &【题解】SP5150
    \(\mathfrak{1st.}\)前言-->题目传送门<--原先这道题的难度是紫，我觉得题目翻译看不懂，就去讨论版发了个贴，然后题管更新了题目翻译，并且把难度降到了蓝……\(\mathfrak{2nd.}\)思路赶时间或嫌啰嗦的可以直接跳到『思路归纳』。我们先从普通并查集开始思考对于删除单点\(x\)，......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99