当前位置：首页 > article >正文

数据结构-并查集专题（2）

article 2024/11/13 9:33:14

一、前言

接（1）完成剩余题目和了解并查集运用求解最小生成树的Kruskal算法

二、专题训练

2.1 题目总览

前四题见（1）

2.2 1568: 并查集-家谱

思路

首先这个题目的描述就有问题，它说每一组的父子关系由两行组成，那样例的第3到第5行你要怎么解释，麻了。这里应该是#开头的是父亲，下面紧跟着的若干行+开头的都是他的儿子。而且这个题也是不适合用我们的模板去解的，因为它需要从字符串映射到字符串，当然你也可以给字符串编个序号这样也可以实现，我这里给出另一种解法，我们用哈希表来实现字符串到字符串的映射。其余的就是并查集的基本操作了

参考代码

#include <bits/stdc++.h>
#include <functional>
using i64 = long long;

using pss = std::pair<std::string,std::string>;

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    std::vector<pss> v;
    pss pair = {"",""};
    std::vector<std::string> query;
    std::string line;
    std::unordered_map<std::string,std::string> fa;
    std::string father,son;

    using Find = std::function<std::string(std::string)>;
    Find find = [&](std::string x)  {
        if(x!=fa[x]) fa[x] = find(fa[x]);
        return fa[x];
    };

    while(std::getline(std::cin,line)) {
        if(line[0]=='#') {
            father = line.substr(1);
            if(fa[father]=="") fa[father] = father;
        }else if(line[0]=='+') {
            son = line.substr(1);
            if(fa[son]=="") {
                fa[son] = find(father);
            }
        }else if(line[0]=='?') {
            query.emplace_back(line.substr(1));
        }else {//line[0]=='$'
            break;
        }
    }

    for(auto &str:query) {
        std::cout << str << ' ' << find(str) << '\n';
    }

    return 0;
}

2.3 1836: 并查集-格子游戏

思路

对于并查集来说，一个节点的值最常见的是一个int，上一题节点的值是一个字符串，这道题节点的值是一个坐标点，当然你可以像上一题一样，写一个坐标的结构体，然后用哈希表将坐标映射到坐标，我这里采用将坐标变换成一个int，然后每次操作时判断，要连接的两个点是否已经在同一个并查集中了，如果是则输出当前的步数，如果不是则将两个节点进行合并，执行到结束，如果游戏仍然没有结束则输出"draw"

参考代码

注意并查集初始化的时候，空间要开大一些

#include <bits/stdc++.h>
using i64 = long long;

struct DisjointSet {
    int _n;
    std::vector<int> _fa,_size;
    DisjointSet(){}
    DisjointSet(int n){
        init(n);
    }
    void init(int n) {
        _fa.resize(n);
        std::iota(_fa.begin(),_fa.end(),0);
        _size.assign(n,1);
    }
    int find(int x) {
        if(x!=_fa[x]) {
            _fa[x] = find(_fa[x]);
        }
        return _fa[x];
    }
    bool same(int x,int y) {
        return find(x)==find(y);
    }
    bool merge(int x,int y) {
        int fx = find(x);
        int fy = find(y);
        if(fx!=fy) {
            _size[fx]+=_size[fy];
            _fa[fy] = fx;
            return true;
        }
        return false;
    }
};

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int n,m;
    std::cin >> n >> m;
    DisjointSet disjointSet = DisjointSet((n+5)*(n+2));
    
    for(int i = 0;i<m;i++) {
        int x1,y1,x2,y2;
        std::cin >> x1 >> y1;
        std::string op;
        std::cin >> op;
        if(op=="D") {
            x2 = x1+1,y2 = y1;
        }else {
            x2 = x1,y2 = y1+1;
        }
        int t1 = n*(x1-1)+y1-1,t2 = n*(x2-1)+y2-1;

        if(!disjointSet.merge(t1,t2)) {
            std::cout << i+1 << '\n';
            return 0;
        }
    }
    std::cout << "draw" << '\n';
    
    return 0;
}

2.4 1837: 并查集-亲戚

思路

此题思路很一般，正常做就行，但是因为数据量的限制，我们写并查集的时候一定要做路径压缩，不然会TLE，直接用我们的模板就行

参考代码

#include <bits/stdc++.h>
using i64 = long long;

struct DisjointSet {
    int _n;
    std::vector<int> _fa,_size;
    DisjointSet(){}
    DisjointSet(int n){
        init(n);
    }
    void init(int n) {
        _fa.resize(n);
        std::iota(_fa.begin(),_fa.end(),0);
        _size.assign(n,1);
    }
    int find(int x) {
        if(x!=_fa[x]) {
            _fa[x] = find(_fa[x]);
        }
        return _fa[x];
    }
    bool same(int x,int y) {
        return find(x)==find(y);
    }
    bool merge(int x,int y) {
        int fx = find(x);
        int fy = find(y);
        if(fx!=fy) {
            _size[fx]+=_size[fy];
            _fa[fy] = fx;
            return true;
        }
        return false;
    }
};

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int n,m;
    std::cin >> n >> m;
    DisjointSet disjointSet = DisjointSet(n+1);

    for(int i = 0;i<m;i++) {
        int x,y;
        std::cin >> x >> y;
        disjointSet.merge(x,y);
    }
    int q;
    std::cin >> q;
    while(q--) {
        int x,y;
        std::cin >> x >> y;
        std::cout << (disjointSet.same(x,y)?"Yes\n":"No\n");
    }
    
    return 0;
}

三、并查集的运用

3.1 最小生成树

最小生成树是一个现实中经常遇到的问题，各个城镇直接修路、修桥，我们力争使用的材料或者经费最少，就需要求出最小生成树

3.2 Prim算法（基于贪心算法，与求最短路的Dijkstra算法类似）

3.3 Kruskal算法（也是基于贪心算法，需要用到并查集）

把带权边按照权值升序排序，开始循环找当前权值最小的边，如果两个节点不在同一个并查集中，则将它们合并，如果在同一个并查集中，则继续找下一条边。循环结束，如果有n-1条边，则成功找到最小生成树（最小生成树不唯一，但最后的权值和最小是唯一的），如果循环结束，找不到n-1条边，则不存在最小生成树

3.3.1 例题1 AcWing 859. Kruskal算法求最小生成树

思路

没啥好说的，是一个模板题

参考代码

#include <bits/stdc++.h>
using i64 = long long;

struct Edge {
    int _x, _y, _w;
    Edge(int x, int y, int w) : _x(x), _y(y), _w(w) {}
    bool operator<(const Edge& edge2) const {
        return _w < edge2._w;
    }
};

struct DisjointSet {
    int _n;
    std::vector<int> _fa,_size;
    DisjointSet(){}
    DisjointSet(int n){
        init(n);
    }
    void init(int n) {
        _fa.resize(n);
        std::iota(_fa.begin(),_fa.end(),0);
        _size.assign(n,1);
    }
    int find(int x) {
        if(x!=_fa[x]) {
            _fa[x] = find(_fa[x]);
        }
        return _fa[x];
    }
    bool same(int x,int y) {
        return find(x)==find(y);
    }
    bool merge(int x,int y) {
        int fx = find(x);
        int fy = find(y);
        if(fx!=fy) {
            _size[fx]+=_size[fy];
            _fa[fy] = fx;
            return true;
        }
        return false;
    }
};

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int n, m;
    std::cin >> n >> m;
    std::vector<Edge> edges;
    DisjointSet disjointSet(n);

    for (int i = 0; i < m; ++i) {
        int x, y, w;
        std::cin >> x >> y >> w;
        edges.emplace_back(x, y, w);
    }
    std::sort(edges.begin(), edges.end());

    int ans = 0, cnt = 0;
    for (const auto& edge : edges) {
        if (disjointSet.merge(edge._x, edge._y)) {
            ans += edge._w;
            ++cnt;
            if (cnt == n - 1) break;
        }
    }
    std::cout << (cnt < n - 1 ? "impossible" : std::to_string(ans)) << '\n';

    return 0;
}

3.3.2 例题2 最小生成树-最优布线问题

思路

题目的输入是邻接矩阵的形式，我们把它转换成边存储，然后再用Kruskal算法即可，当然这个题用Prim算法更合适

参考代码1（Kruskal算法）

#include <bits/stdc++.h>
using i64 = long long;

struct Edge {
    int _x,_y,_w;
    Edge(int x,int y,int w):_x(x),_y(y),_w(w){}
    bool operator < (const Edge& edge2) const {
        return _w<edge2._w;
    }
};

struct DisjointSet {
    int _n;
    std::vector<int> _fa,_size;
    DisjointSet(){}
    DisjointSet(int n){
        init(n);
    }
    void init(int n) {
        _fa.resize(n);
        std::iota(_fa.begin(),_fa.end(),0);
        _size.assign(n,1);
    }
    int find(int x) {
        if(x!=_fa[x]) {
            _fa[x] = find(_fa[x]);
        }
        return _fa[x];
    }
    bool same(int x,int y) {
        return find(x)==find(y);
    }
    bool merge(int x,int y) {
        int fx = find(x);
        int fy = find(y);
        if(fx!=fy) {
            _size[fx]+=_size[fy];
            _fa[fy] = fx;
            return true;
        }
        return false;
    }
};

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int n;
    std::cin >> n;
    std::vector<Edge> edges;
    DisjointSet disjointSet = DisjointSet(n+1);

    for(int i = 1;i<=n;i++) {
        for(int j = 1;j<=n;j++) {
            int w;
            std::cin >> w;
            if(j>=i) {
                edges.emplace_back(i,j,w);
            }
        }
    }

    std::sort(edges.begin(),edges.end());

    int ans = 0;
    for(int i = 0;i<edges.size();i++) {
        int x = edges[i]._x,y = edges[i]._y,w = edges[i]._w;
        int fx = disjointSet.find(x),fy = disjointSet.find(y);
        if(disjointSet.merge(fx,fy)) {
            ans+=w;
        }
    }
    std::cout << ans << '\n';
    
    return 0;
}

参考代码2（Prim算法）

#include <iostream>
#include <cstring>
#include <type_traits>

template<typename T1,typename T2>
typename std::common_type<T1,T2>::type min(T1 num1,T2 num2){
	return num1>num2?num2:num1;
}
int main(){
	std::cin.tie(nullptr)->sync_with_stdio(false);

	constexpr int MAX_N = 1e2+5,INF = 0x3f3f3f3f;
	int g[MAX_N][MAX_N];
	int dist[MAX_N];
	bool vis[MAX_N] {};

	int n;std::cin >> n;
	for(int i = 1;i<=n;++i){
		for(int j = 1;j<=n;++j){
			std::cin >> g[i][j];
		}
	}

	auto prim = [&]()->int{
		memset(dist,0x3f,sizeof dist);
		int res = 0;
		dist[1] = 0;
		for(int i = 0;i<n;++i){
			int t = -1;
			for(int j = 1;j<=n;++j){
				if(!vis[j]&&(t==-1||dist[j]<dist[t])) t = j;
			}
			if(dist[t]==INF) return INF;
			vis[t] = true;
			res+=dist[t];
			for(int j = 1;j<=n;++j) dist[j]=min(dist[j],g[t][j]);
		}
		return res;
	};

	std::cout << prim() << '\n';

	return 0;
}

查看全文

http://www.kler.cn/a/387296.html