并查集相关

并查集

参考链接
注意，实现的功能是添加边，将一条边两端的两个元素归为一个组合中的两个元素
在实现 find 函数的过程中，我们知道，通过递归的方式，不断获取father数组下标对应的数值，最终找到这个集合的根
在递归的过程中，让 father[u] 接住递归函数 find(father[u]) 的返回结果

int n = 1005; // n根据题目中节点数量而定，一般比节点数量大一点就好
vector<int> father = vector<int> (n, 0); // C++里的一种数组结构

// 并查集初始化
void init() {
    for (int i = 0; i < n; ++i) {
        father[i] = i;
    }
}
// 并查集里寻根的过程
int find(int u)
{
    if(u != father[u]) // 如果自己不是根节点
    {
		// 将自己的根节点直接改为最顶的根节点
        father[u] = find(father[u]);
    }
    return father[u];
}

// 判断 u 和 v是否找到同一个根
bool isSame(int u, int v) {
    u = find(u);
    v = find(v);
    return 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;
}

Leetcode 1971. 寻找图中是否存在路径

此题的原理就是将所有的边加入并查集，最后查找二者是否对应同一个祖先

class Solution {
private:
    int n = 200005; // 节点数量 20000
    vector<int> father = vector<int> (n, 0); // C++里的一种数组结构

    // 并查集初始化
    void init() {
        for (int i = 0; i < n; ++i) { father[i] = i;
        }
    }
    // 并查集里寻根的过程
    int find(int u) {
        return u == father[u] ? u : father[u] = find(father[u]);
    }

    // 判断 u 和 v是否找到同一个根
    bool isSame(int u, int v) {
        u = find(u);
        v = find(v);
        return 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;
    }

public:
    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        init();
        for (int i = 0; i < edges.size(); i++) {
            join(edges[i][0], edges[i][1]);
        }
        return isSame(source, destination);

    }
};

Leetcode 684. 冗余连接

此题同样是使用并查集
主要是在插入之前检测是否边两端的节点已经是一个集合中的了

如果不是的话就插入，是的话说明边是冗余的

class Solution {
private:
    int n = 1005; // 节点数量3 到 1000
    vector<int> father = vector<int> (n, 0); // C++里的一种数组结构

    // 并查集初始化
    void init() {
        for (int i = 0; i < n; ++i) {
            father[i] = i;
        }
    }
    // 并查集里寻根的过程
    int find(int u) {
        return u == father[u] ? u : father[u] = find(father[u]);
    }
    // 判断 u 和 v是否找到同一个根
    bool isSame(int u, int v) {
        u = find(u);
        v = find(v);
        return 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;
}
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        init();
        for (int i = 0; i < edges.size(); i++) {
            if (isSame(edges[i][0], edges[i][1])) return edges[i];
            else join(edges[i][0], edges[i][1]);
        }
        return {};
    }
};

最小生成树问题

此题是找能将所有点联通的最小代价的所有路径

使用kruskal算法

初始化一个并查集，最开始每个节点都是独立的
将所有路径加入一个代价从小到大的最小堆，每次取出一个路径

如果路径两端的点在一个集合中，则忽略，如果不在，则该路径是必须的路径，加入需要的路径集合中并且加入总代价中

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

vector<int> father;

struct edge
{
    int start;
    int end;
    int val;
};

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

bool isSame(int u, int v)
{
    return find(u) == find(v);
}

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

int main()
{
    int n, e;
    cin>>n>>e;
    father = vector<int>(n+1, 0);
    for(int i = 1 ;i<=n; ++i)
    {
        father[i] = i;
    }
    auto cmp = [](const edge& a, const edge& b)
    {
        return a.val > b.val;
    };
    // int conned = 1;
    priority_queue<edge, vector<edge>, decltype(cmp)> pq(cmp);
    struct edge tmp;
    for(int i = 0; i<e; ++i)
    {
        cin>>tmp.start>>tmp.end>>tmp.val;
        pq.push(tmp);
    }
    int sum = 0;
    while(pq.size())
    {
        tmp = pq.top();
        // cout<<tmp.val<<endl;
        pq.pop();
        if(!isSame(tmp.start, tmp.end))
        {
            sum+=tmp.val;
            join(tmp.start, tmp.end);
        }
    }
    cout<<sum<<endl;
}

41. 岛屿数量（第四期模拟笔试）

链接

此题是标准的并查集问题

#include <iostream>
#include <vector>
#include <cstdlib>

using namespace std;

int find(vector<int>& father, int u)
{
    if(u!=father[u])
    {
        father[u] = find(father, father[u]);
    }
    return father[u];
}

bool isSame(int u, int v, vector<int>& father)
{
    return find(father, u) == find(father, v);
}

bool join(vector<int>& father, int u, int v)
{
    u = find(father, u);
    v = find(father, v);
    if(u == v)return false;
    else father[v] = u;
    return true;
}

int main()
{
    int m, n, k;
    cin>>m>>n>>k;
    vector<vector<int>> map(m, vector<int>(n, 0));
    vector<int> father(m*n, 0);
    for(int i = 0; i<m*n; ++i)
    {
        father[i] = i;
    }
    int a, b;
    int cnt = 0;
    for(int i = 0; i<k; ++i)
    {
        cin>>a>>b;
        
        if(a>=m || b>=n || a<0 || b<0)
        {
            cout<<cnt<<' ';
            continue;
        }
        if(!map[a][b]) ++cnt;
        map[a][b] = 1;
        bool tmp = false;
        if(a>0 && map[a-1][b])
        {
            tmp = join(father, (a-1)*m+b, a*m+b);
            cnt-=tmp;
        }
        if(b>0 && map[a][b-1])
        {
            tmp = join(father, (a*m+b-1), a*m+b);
            cnt-=tmp;
        }
        if(a<m-1 && map[a+1][b])
        {
            tmp = join(father, (a+1)*m+b, a*m+b);
            cnt-=tmp;
        }
        if(b<n-1 && map[a][b+1])
        {
            tmp =join(father, a*m+b+1, a*m+b);
            cnt-=tmp;
        }
        cout<<cnt<<' ';
    }
}