跳转至

Mfset

并查集（Union-Find）是一种处理不相交集合/能够快速解决动态连通性问题的数据结构。并查集支持两种操作：find 和 union。还有一个额外的辅助操作 makeSet，它是初始化每个元素所在的集合的。

以下是并查集的主要操作：

  1. makeSet(x): 初始化操作，使得元素x形成一个新的集合。在这个操作中，元素x是自己集合的代表。
  2. find(x): 返回元素x所在集合的代表元素，也就是找到它所在的集合（或等价类）。
  3. union(x, y): 如果元素x和元素y不在同一个集合中，那么合并它们所在的两个集合。

这些操作可以很容易地在C++中实现，如下所示：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<bits/stdc++.h>
using namespace std;

const int MAX = 1e5;
int parent[MAX];
int rank_[MAX];

void makeSet(int x) {
    parent[x] = x;
    rank_[x] = 0;
}

int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]); // Path compression
    }
    return parent[x];
}

void unionSets(int x, int y) {
    int xRoot = find(x);
    int yRoot = find(y);
    // Union by rank
    if (rank_[xRoot] < rank_[yRoot]) {
        parent[xRoot] = yRoot;
    } else if (rank_[xRoot] > rank_[yRoot]) {
        parent[yRoot] = xRoot;
    } else {
        parent[yRoot] = xRoot;
        rank_[xRoot] = rank_[xRoot] + 1;
    }
}

int main() {
    for (int i = 0; i < MAX; i++) {
        makeSet(i);
    }
    // Add unions as required
    // unionSets(a, b);
    return 0;
}

举例：

例如，我们有10个元素：0, 1, 2, ..., 9。初始化的时候，每个元素各自都属于一个单独的集合。然后，我们执行以下的合并操作：

  1. 合并元素1和元素2所在的集合
  2. 合并元素3和元素4所在的集合
  3. 合并元素1和元素3所在的集合
  4. 合并元素5和元素6所在的集合

下面是完成这个任务的C++代码：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>
using namespace std;

const int MAX = 10;
int parent[MAX];
int rank_[MAX];

void makeSet(int x) {
    parent[x] = x;
    rank_[x] = 0;
}

int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]); // Path compression
    }
    return parent[x];
}

void unionSets(int x, int y) {
    int xRoot = find(x);
    int yRoot = find(y);
    // Union by rank
    if (rank_[xRoot] < rank_[yRoot]) {
        parent[xRoot] = yRoot;
    } else if (rank_[xRoot] > rank_[yRoot]) {
        parent[yRoot] = xRoot;
    } else {
        parent[yRoot] = xRoot;
        rank_[xRoot] = rank_[xRoot] + 1;
    }
}

int main() {
    for (int i = 0; i < MAX; i++) {
        makeSet(i);
    }
    unionSets(1, 2);
    unionSets(3, 4);
    unionSets(1, 3);
    unionSets(5, 6);

    for(int i = 0; i < MAX; i++) {
        cout << "Element: " << i << " set: " << find(i) << endl;
    }

    return 0;
}

在这个代码中，我们首先使用makeSet函数初始化10个元素，然后执行一系列的unionSets操作来合并一些集合。最后，我们打印每个元素所在的集合的代表元素，代表元素也就是这个集合的标识。

当运行这个代码，输出如下：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
Element: 0 set: 0
Element: 1 set: 1
Element: 2 set: 1
Element: 3 set: 1
Element: 4 set: 1
Element: 5 set: 5
Element: 6 set: 5
Element: 7 set: 7
Element: 8 set: 8
Element: 9 set: 9

从输出中我们可以看到，元素1, 2, 3, 4在同一个集合中，元素5和6在同一个集合中，其他元素各自在一个集合中。

应用案例：

​ 1.网络连通性问题：在网络中，节点之间的连通性是非常重要的问题。并查集可以快速地查询两个节点是否连通，也可以将两个不连通的网络合并。判断网络连通性的一个常见方法是使用深度优先搜索（DFS）或广度优先搜索（BFS），但在大型网络或频繁查询的情况下，这种方法可能效率较低。在这种情况下，一种更有效的方法是使用并查集。

​ 并查集是一种可以动态连接和查询任意两个节点是否连通的数据结构。这在处理网络连通性的问题中特别有用，因为它可以在几乎恒定的时间内执行这两个操作。

下面是用并查集判断网络连通性的C++代码：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>
using namespace std;

const int MAX = 10000;
int parent[MAX];

void makeSet(int x) {
    parent[x] = x;
}

int findSet(int x) {
    if (x != parent[x]) {
        parent[x] = findSet(parent[x]); 
    }
    return parent[x];
}

void unionSets(int x, int y) {
    int xRoot = findSet(x);
    int yRoot = findSet(y);
    if (xRoot != yRoot) {
        parent[xRoot] = yRoot;
    }
}

bool isConnected(int x, int y) {
    return findSet(x) == findSet(y);
}

int main() {
    for (int i = 0; i < MAX; i++) {
        makeSet(i);
    }

    unionSets(1, 2);
    unionSets(2, 3);
    unionSets(4, 5);

    cout << "1 and 3 are connected: " << (isConnected(1, 3) ? "Yes" : "No") << endl;
    cout << "1 and 4 are connected: " << (isConnected(1, 4) ? "Yes" : "No") << endl;

    return 0;
}

​ 这个程序首先通过makeSet函数初始化每个节点，使每个节点自身成为一个单独的集合。然后，通过unionSets函数将一些节点（或网络中的边）连接在一起。isConnected函数用于检查两个节点是否连接。如果两个节点属于同一集合，那么它们就是连接的。

​ 注意，findSet函数使用了路径压缩的策略，它在查找集合的代表元素的同时，将集合中的每个元素的父节点都直接指向代表元素，从而优化了后续的查找操作。

2.图算法：并查集在解决图的问题时非常有用，特别是在求解最小生成树的Kruskal算法中。并查集可以快速判断两个节点是否在同一个连通子图内，防止形成环。

​ Kruskal算法是一种贪心算法，用于在连通图中找出最小生成树。其基本思想是按照边的权重（从小到大）将边添加到生成树中，但是在添加边的同时，检查是否形成了环，如果形成了环，则不添加此边。

下面是Kruskal算法的步骤：

  1. 将所有的边按照权重大小进行排序。
  2. 初始化一个空的最小生成树。
  3. 遍历排序后的边，将边加入最小生成树。如果加入这条边会导致环出现，就不加入，否则就加入。
  4. 重复步骤3，直到最小生成树中有n - 1条边为止，或者所有的边都被检查过为止。这里，n是图中节点的数量。

以下是用C++实现的Kruskal算法：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<bits/stdc++.h>
using namespace std;

struct Edge {
    int u, v, weight;
    bool operator<(Edge const& other) {
        return weight < other.weight;
    }
};

vector<int> parent, rank_;
vector<Edge> edges;

void makeSet(int v) {
    parent[v] = v;
    rank_[v] = 0;
}

int findSet(int v) {
    if (v == parent[v])
        return v;
    return parent[v] = findSet(parent[v]);
}

void unionSets(int a, int b) {
    a = findSet(a);
    b = findSet(b);
    if (a != b) {
        if (rank_[a] < rank_[b])
            swap(a, b);
        parent[b] = a;
        if (rank_[a] == rank_[b])
            ++rank_[a];
    }
}

void kruskal(int n) {
    sort(edges.begin(), edges.end());

    for (int i = 0; i < n; i++)
        makeSet(i);

    for (Edge e : edges) {
        if (findSet(e.u) != findSet(e.v)) {
            cout << e.u << " " << e.v << "\n";  
            unionSets(e.u, e.v);
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    parent.resize(n);
    rank_.resize(n);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        edges.push_back({u, v, w});
    }

    kruskal(n);

    return 0;
}

​ 这段代码中定义了一个表示边的结构体Edge，包括两个节点和权重，然后实现了Kruskal算法的步骤。在kruskal函数中，首先按照权重对所有边进行排序，然后遍历每条边，如果这条边连接的两个节点不在同一个集合中，那么这条边就可以加入最小生成树，同时合并这两个节点的集合。

3.像素连通性：在图像处理中，有时需要确定两个像素是否连通。可以将每个像素视为图的一个节点，相邻的像素之间有边。使用并查集，可以快速地找出所有连通的像素块。

像素连通性问题常常出现在图像处理中，一般会使用深度优先搜索(DFS)或广度优先搜索(BFS)来解决。

​ 以下是一个简单的C++示例，演示了如何使用深度优先搜索(DFS)来寻找和指定像素连通的所有像素。在这个例子中，我们将图像视为一个二维数组，每个像素是一个元素，相邻的像素是指在上下左右四个方向相邻的元素：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;

const int MAX = 100;
int visited[MAX][MAX];
vector<vector<int>> image; // Assume this is given

// These arrays are used to get row and column numbers of 4 neighbours of a given cell
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

// A function to check if a given cell (row, col) can be included in DFS
bool isSafe(int row, int col, int prevColor) {
    return (row >= 0) && (row < image.size()) && (col >= 0) && (col < image[0].size()) && (image[row][col] == prevColor) && !visited[row][col];
}

void dfs(int row, int col, int prevColor) {
    visited[row][col] = 1;
    // Recur for all connected neighbours
    for (int k = 0; k < 4; ++k) {
        if (isSafe(row + dx[k], col + dy[k], prevColor)) {
            dfs(row + dx[k], col + dy[k], prevColor);
        }
    }
}

int main() {
    int startRow = 0, startCol = 0; // Assume these are given
    memset(visited, 0, sizeof(visited));
    dfs(startRow, startCol, image[startRow][startCol]);
    return 0;
}

​ 以上代码首先定义了一个visited二维数组，用于标记每个像素是否已经访问过。然后在dfs函数中，首先标记当前像素为已访问，然后递归地访问该像素的所有未访问过的相邻像素。

​ 请注意这只是一个基础的实现，对于大规模的图像，可能需要进一步优化。例如，可以使用并查集来快速判断两个像素是否连通，或者可以使用迭代的深度优先搜索或广度优先搜索来避免递归可能导致的栈溢出问题。

更优的解法：并查集是一种能够高效处理像素连通性问题的数据结构。下面是一个使用并查集处理图像像素连通性的C++例子：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>
using namespace std;

const int MAX = 10000;
vector<int> parent(MAX);
vector<vector<int>> image; // Assume this is given

// Initialize the disjoint set
void makeSet(int v) {
    parent[v] = v;
}

// Find the root of the set that element v belongs to
int findSet(int v) {
    if (v == parent[v])
        return v;
    return parent[v] = findSet(parent[v]); // Path compression
}

// Union two sets
void unionSets(int a, int b) {
    a = findSet(a);
    b = findSet(b);
    if (a != b) {
        parent[b] = a;
    }
}

// Check if two elements are in the same set
bool isConnected(int a, int b) {
    return findSet(a) == findSet(b);
}

void connectPixels() {
    int n = image.size(), m = image[0].size();
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (i > 0 && image[i][j] == image[i-1][j])
                unionSets(i*m+j, (i-1)*m+j);
            if (j > 0 && image[i][j] == image[i][j-1])
                unionSets(i*m+j, i*m+(j-1));
        }
    }
}

int main() {
    for (int i = 0; i < MAX; ++i) {
        makeSet(i);
    }

    // Assume the image is given
    connectPixels();

    // Now we can check if any two pixels are connected in constant time
    cout << isConnected(0, 1) << "\n";
    cout << isConnected(1, 2) << "\n";

    return 0;
}

​ 在这个代码中，我们将每个像素视为一个独立的元素，并使用并查集来管理这些元素的连接关系。在connectPixels函数中，我们扫描每个像素，如果某像素与其上方或左方的像素颜色相同，则将它们连接在一起。

​ 注意，这里我们将二维的像素坐标转换成一维的编号来使用并查集。比如像素(i, j)的编号是i*m+j，其中m是图像的宽度。这样我们就可以直接使用并查集来管理像素的连通关系。

​ 最后，在主函数中，我们可以使用isConnected函数来在常数时间内检查任意两个像素是否连通。

4.等价类划分：在许多应用中，需要根据某些条件将对象分为几个等价类。并查集可以在动态添加等价关系时，快速地划分等价类。

并查集是一种数据结构，它能够处理一些不交集合的合并及查询问题。它的主要操作有：

  1. 查找元素所在的集合，通常使用 find 操作。
  2. 合并两个集合，通常使用 union 操作。

以下是一个使用并查集处理等价类划分问题的基础的C++例子：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
using namespace std;

const int MAX = 10000;
vector<int> parent(MAX), rank_(MAX);

// Initialize the disjoint set
void makeSet(int v) {
    parent[v] = v;
    rank_[v] = 0;
}

// Find the root of the set that element v belongs to
int findSet(int v) {
    if (v == parent[v])
        return v;
    return parent[v] = findSet(parent[v]); // Path compression
}

// Union two sets
void unionSets(int a, int b) {
    a = findSet(a);
    b = findSet(b);
    if (a != b) {
        if (rank_[a] < rank_[b])
            swap(a, b);
        parent[b] = a;
        if (rank_[a] == rank_[b])
            ++rank_[a];
    }
}

int main() {
    for (int i = 0; i < MAX; ++i) {
        makeSet(i);
    }

    // Assume we have some pairs of equivalent elements
    vector<pair<int, int>> equivalentPairs = {{1, 2}, {2, 3}, {4, 5}, {6, 7}, {8, 9}};

    // Merge equivalent pairs
    for (auto pair : equivalentPairs) {
        unionSets(pair.first, pair.second);
    }

    // Now each disjoint set represents an equivalence class
    // We can use findSet to determine the equivalence class of an element
    cout << findSet(2) << "\n"; // Output: 1
    cout << findSet(5) << "\n"; // Output: 4

    return 0;
}

​ 在这段代码中，我们使用了并查集来管理等价元素的关系。每个并查集的集合都代表一个等价类。我们可以通过 findSet 函数来找到一个元素所在的等价类。

​ 这只是一个基本的例子，实际的等价类划分问题可能更复杂，可能需要根据实际的等价关系来调整并查集的使用方法。

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用