分类 图论 下的文章

并查集

1

并查集就是解决若干元素所属的集合关系的一类问题
简单来说并查集一般有以下几个操作:将两个元素所在的集合合并;查找某个元素所在的集合(根节点)

2

初始化

一般的,在初始情况下,每个元素自成一个集合,这个集合的根节点就是元素本身。
并查集-1.png
用数组fa[]来记录该并查集的话,初始化应该是这样的:

void init(int x) {  //并查集元素个数
    for (int i = 1; i <= x; ++ i) fa[i] = i;
}

查找根节点

简单的,不断顺着数组fa[]“逆流而上”查找,直到fa[x] = x时就找到根节点了,可以用递归或者循环实现。

int get(int x) {  // 获取x的根节点
    if (fa[x] = x) return x;  //找到根节点后返回答案
    return get(fa[x]);
}

注意,并查集有可能遇到这样的糟糕情况:
并查集-4.png
当我们试图查找节点5的根节点时,我们需要遍历整个并查集才能找到节点1。在百万或以上的数据规模中,这种无意义的时间消耗是致命的,所以我们需要路径压缩,将上图的情况优化成这样:
并查集-5.png
这样从节点5就可以一次性找到节点1了。
代码优化后实现如下

int get(int x) {  // 获取x的根节点
    if (fa[x] = x) return x;  //找到根节点后返回答案
    return fa[x] = get(fa[x]); //在查找过程中将所有经过的点一并连接到根节点上
}

合并

将两个并查集合并,只要统一它们的父亲节点即可。当两个并查集拥有同一个根节点的时候,意味着它们是一个并查集。
并查集-2.png
举例,如图,合并并查集{1,2,3}和并查集{4,5}只需要将{1,2,3}的根节点置为4或将{4,5}的根节点置为1
像这样:
并查集-3.png
代码实现如下

void merge(int x, int y) { //将元素x和元素y所在的集合合并
    fa[get(x)] = get(y);
    //fa[get(y)] = get(x);  这也是一个可行的方案
}

3 例题

洛谷P3367为例

题目描述

如题,现在有一个并查集,你需要完成合并和查询操作。

输入输出格式

输入格式:

第一行包含两个整数N、M,表示共有N个元素和M个操作。
接下来M行,每行包含三个整数Zi、Xi、Yi
当Zi=1时,将Xi与Yi所在的集合合并
当Zi=2时,输出Xi与Yi是否在同一集合内,是的话输出Y;否则话输出N

输出格式:

如上,对于每一个Zi=2的操作,都有一行输出,每行包含一个大写字母,为Y或者N

输入输出样例

输入样例#1:

4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4

输出样例#1:

N
Y
N
Y

说明

时空限制:1000ms,128M
数据规模:
对于30%的数据,N<=10,M<=20;
对于70%的数据,N<=100,M<=1000;
对于100%的数据,N<=10000,M<=200000。

AC代码

#include <iostream>

int fa[10003];

void init(int x) {
    for (int i = 1; i <= x; ++ i) fa[i] = i;
}
int get(int x) {
    if (fa[x] == x) return x;
    return fa[x] = get(fa[x]);
}
void merge(int x, int y) {
    fa[get(x)] = get(y);
}

int main () {
    std::ios::sync_with_stdio(false);
    register int i, j;
    int n, m, z, x, y;
    
    std::cin >> n >> m;
    init(n);
    for (i = 1; i <= m; ++ i) {
        std::cin >> z >> x >> y;
        if (z == 1) merge(x, y);
        if (z == 2) {
            if (get(x) == get(y)) std::cout << "Y\n";
            else std::cout << "N\n";
        }
    }
    
    return 0;
}

单元最短路径问题

单元最短路问题概述

1

单元最短路是在图论中求两个单元(节点)之间边权值和最小的一个方案。
通常使用“松弛”来解决此类问题。
对于节点A,B:如果使AB中间增加中转节点C,那么:如果AC+CB权值和小于AB的权值,则AB的更短距离为AC+CB的距离
如此反复,直到保证任意两点之间都求出最短权值和为止

在程序中通常像这样实现:

for(...) {  //遍历节点
    if (weight[i][j] > weight[i][x] + weight[x][j]) {  //x作为中转节点
        dis[i][j] = weight[i][x] + weight[x][j]  //用中转节点松弛
    }
}

2 Floyed算法

一个复杂度为O(N^3)的多元最短路径算法算法
原理是直接枚举所有的起点,终点,以及它们之间的中转点并不断的尝试松弛操作

#include <iostream>

int G[1003][1003], dis[1003][1003];

int main () {
    std::ios::sync_with_stdio(false);
    int i, j;
    int n, m, s, f, g, w, x, y;
    std::cin >> n >> m >> s;

    for (i = 1; i <= n; ++ i) {
        for (j = 1; j <= n; ++ j) {
            dis[i][j] = 2147483647;
        }
    }

    for (i = 1; i <= m; ++ i) {
        std::cin >> f >> g >> w;
        G[f][g]  = dis[f][g] = w;
    }

    for (int k = 1; k <= n; ++ k)
        for (i = 1; i <= n; ++ i)
            for (j = 1; j <= n; ++ j)
                if (G[i][j] > G[i][k] + G[k][j]) dis[i][j] = G[i][k] + G[k][j];

    dis[s][s] = 0;
    for (i = 1; i <= n; ++ i) std::cout << dis[s][i] << ' ';

    return 0;
}

3 SPFA算法

SPFA借助队列优化,本质也是一个不断松弛的过程
更加适合稀疏图,但是在稠密图面前可能退化到O(VE)的复杂度

#include <iostream>
#include <queue>
#include <vector>
#include <string.h>

struct node {
    int u, v, w;
};

std::queue<int> Q;
std::vector<node> v[10001];
int dis[10001], count[10001];
bool inqueue[10001];

void SPFA(int start) {
    int temp, temp2, temp3, i;

    memset(dis, 127, sizeof(dis));
    dis[start] = 0;
    ++ count[start];Q.push(start);
    while(!Q.empty()) {
        temp = Q.front();
        Q.pop();
        inqueue[temp] = false;
        for (i = 1; i <= v[temp].size(); ++ i) {
            temp2 = v[temp][i].v;
            temp3 = v[temp][i].w;
            if (dis[temp] + temp3 < dis[temp2]) {
                dis[temp2] = dis[temp] + temp3;
                if (!inqueue[temp2]) {
                    Q.push(temp2);
                    inqueue[temp2] = true;
                }
            }
        }
    }
}

int main() {
    int m, n, temp, temp2, temp3;
    std::cin >> n >> m;
    for (int i = 1; i <= m; ++ i) {
        std::cin >> temp >> temp2 >> temp3;
        v[temp].push_back({temp, temp2, temp3});
    }

    SPFA(1);

    std::cout << dis[n];

    return 0;
}