跳转至

Disjoint set

并查集（Disjoint Set）是一种用于处理不相交集合的数据结构。它主要支持两种操作：合并（Union）和查找（Find）。

并查集的基本思想是将每个元素看作一个节点，并使用树来表示每个集合。每个节点都有一个指向父节点的指针，如果一个节点的父节点指向自身，则表示该节点为根节点，即该集合的代表元素。

并查集的常见应用包括判断两个元素是否属于同一个集合、判断图中是否存在环、求解图的连通性问题、社交网络中的好友关系问题、最小生成树算法中边的选择、解决等价关系、图像分割问题等。

1、判断两个元素是否属于同一个集合

以下是一个判断两个元素是否属于同一个集合的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
60
61
#include <iostream>
#include <vector>

using namespace std;

// 并查集类
class DisjointSet {
private:
    vector<int> parent;  // 存储每个节点的父节点

public:
    // 构造函数
    DisjointSet(int size) {
        parent.resize(size);

        // 初始化，每个节点的父节点指向自身
        for (int i = 0; i < size; i++) {
            parent[i] = i;
        }
    }

    // 查找根节点（代表元素）
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);  // 路径压缩，将x的父节点直接指向根节点
        }
        return parent[x];
    }

    // 合并两个集合
    void unionSets(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX != rootY) {
            parent[rootX] = rootY;  // 将一个根节点的父节点指向另一个根节点
        }
    }

    // 判断两个元素是否属于同一个集合
    bool isConnected(int x, int y) {
        return find(x) == find(y);
    }
};

int main() {
    int n = 5;  // 元素个数

    DisjointSet ds(n);

    // 进行一些合并操作
    ds.unionSets(0, 2);
    ds.unionSets(1, 4);
    ds.unionSets(3, 0);

    // 判断元素是否属于同一个集合
    cout << "0 和 4 是否属于同一个集合：" << ds.isConnected(0, 4) << endl;
    cout << "1 和 3 是否属于同一个集合：" << ds.isConnected(1, 3) << endl;

    return 0;
}

上述代码中，我们定义了一个DisjointSet类来实现并查集。首先创建一个大小为n的并查集对象，然后通过unionSets函数进行合并操作，通过isConnected函数判断两个元素是否属于同一个集合。

在示例中，我们合并了元素0和2、元素1和4、元素3和0，并判断了元素0和4、元素1和3是否属于同一个集合。输出结果为：0 和 4 是否属于同一个集合：1（是），1 和 3 是否属于同一个集合：0（否）。

2、判断无向图中是否存在环

使用并查集来判断无向图中是否存在环的解法如下：

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <iostream>
#include <vector>

using namespace std;

class UnionFind {
private:
    vector<int> parent;  // 存储每个节点的父节点

public:
    // 构造函数
    UnionFind(int n) {
        parent.resize(n);
        // 初始化，每个节点的父节点指向自身
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    // 查找根节点（代表元素）
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);  // 路径压缩，将x的父节点直接指向根节点
        }
        return parent[x];
    }

    // 合并两个集合
    void unionSets(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX == rootY) {
            // 根节点相同，说明已经形成环路
            cout << "图中存在环" << endl;
        } else {
            parent[rootX] = rootY;  // 将一个根节点的父节点指向另一个根节点
        }
    }
};

bool isCyclic(vector<vector<int>>& graph) {
    int numVertices = graph.size();
    UnionFind uf(numVertices);

    for (int i = 0; i < numVertices; i++) {
        for (int j : graph[i]) {
            int root1 = uf.find(i);
            int root2 = uf.find(j);

            if (root1 == root2) {
                // 根节点相同，说明已经形成环路
                return true;
            } else {
                uf.unionSets(root1, root2);
            }
        }
    }

    return false;
}

int main() {
    int numVertices = 5;
    vector<vector<int>> graph(numVertices);

    // 添加图的边
    graph[0].push_back(1);
    graph[1].push_back(0);
    graph[1].push_back(2);
    graph[2].push_back(1);
    graph[2].push_back(3);
    graph[3].push_back(2);
    graph[3].push_back(4);
    graph[4].push_back(3);

    bool hasCycle = isCyclic(graph);

    if (hasCycle) {
        cout << "图中存在环" << endl;
    } else {
        cout << "图中不存在环" << endl;
    }

    return 0;
}

在这个解法中，我们使用并查集来判断图中是否存在环。首先创建一个并查集对象uf，每个节点初始时都是独立的集合。然后遍历无向图的所有边，对于每条边的两个节点，通过并查集的find和unionSets操作进行合并或判断是否属于同一个集合。如果两个节点的根节点相同，说明已经形成环路，输出结果为“图中存在环”。

示例代码中给定的图包含5个节点和边。运行代码会得到输出结果：图中存在环。这意味着判断的无向图包含环路。

使用并查集来判断无向图中是否存在环路的时间复杂度为O(E * α(V))，其中E是边的数量，V是节点的数量，α是Ackermann函数的反函数。

3、图的连通性问题

图的连通性问题可以通过并查集来解决。下面是使用并查集判断无向图是否连通的示例代码：

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <iostream>
#include <vector>

using namespace std;

// 并查集类
class DisjointSet {
private:
    vector<int> parent;  // 存储每个节点的父节点

public:
    // 构造函数
    DisjointSet(int size) {
        parent.resize(size);

        // 初始化，每个节点的父节点指向自身
        for (int i = 0; i < size; i++) {
            parent[i] = i;
        }
    }

    // 查找根节点（代表元素）
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);  // 路径压缩，将x的父节点直接指向根节点
        }
        return parent[x];
    }

    // 合并两个集合
    void unionSets(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX != rootY) {
            parent[rootX] = rootY;  // 将一个根节点的父节点指向另一个根节点
        }
    }
};

// 判断无向图是否连通
bool isGraphConnected(vector<vector<int>>& graph) {
    int n = graph.size();

    DisjointSet ds(n);  // 创建并查集对象

    // 遍历图的边进行合并操作
    for (int u = 0; u < n; u++) {
        for (int v : graph[u]) {
            ds.unionSets(u, v);
        }
    }

    // 判断图中的所有边是否都在同一个集合中
    for (int u = 1; u < n; u++) {
        if (!ds.isConnected(0, u)) {
            return false;
        }
    }

    return true;
}

int main() {
    int n = 5;  // 图的节点数
    vector<vector<int>> graph(n);  // 存储图的邻接表形式

    // 添加边，构建无向图
    graph[0] = {1, 2};
    graph[1] = {0, 2};
    graph[2] = {0, 1};
    graph[3] = {4};
    graph[4] = {3};

    // 判断图是否连通
    bool connected = isGraphConnected(graph);

    cout << "图的连通性：" << (connected ? "连通" : "不连通") << endl;

    return 0;
}

在示例代码中，我们通过创建一个DisjointSet对象，并使用邻接表来表示无向图。然后遍历图的边进行合并操作，最后判断图中的所有边是否都在同一个集合中，以确定图的连通性。

示例中给定的无向图包含5个节点和边，节点0、1、2相互连通，节点3和4也各自连通。运行代码会得到输出结果：图的连通性：不连通。

这种方法适用于判断无向图是否连通的问题。如果图是有向图，需要使用其他算法来判断连通性，如深度优先搜索（DFS）或广度优先搜索（BFS）。

4、社交网络中的好友关系问题

使用并查集来处理社交网络中的好友关系问题，可以方便地判断两个人是否为好友，合并两个人所在的社交圈，并统计每个社交圈的大小。以下是使用并查集解决社交网络中好友关系的示例代码：

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
66
#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

class UnionFind {
private:
    unordered_map<int, int> parent;  // 存储每个节点的父节点
    unordered_map<int, int> size;    // 存储每个社交圈的大小

public:
    // 查找根节点（代表元素）
    int find(int x) {
        if (parent.find(x) == parent.end()) {
            // 若x不在parent中，说明其为新的社交圈，将其设置为自身的父节点
            parent[x] = x;
            size[x] = 1;
        }

        if (parent[x] != x) {
            parent[x] = find(parent[x]);  // 路径压缩，将x的父节点直接指向根节点
        }
        return parent[x];
    }

    // 合并两个社交圈
    void unionSets(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX != rootY) {
            // 将两个社交圈合并，并更新社交圈的大小
            parent[rootX] = rootY;
            size[rootY] += size[rootX];
        }
    }

    // 判断两个人是否为好友
    bool areFriends(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        return rootX == rootY;
    }

    // 获取社交圈的大小
    int getCircleSize(int x) {
        int rootX = find(x);
        return size[rootX];
    }
};

int main() {
    UnionFind uf;

    // 添加好友关系
    uf.unionSets(1, 2);
    uf.unionSets(3, 4);
    uf.unionSets(4, 5);

    cout << "1 和 4 是否为好友？" << (uf.areFriends(1, 4) ? "是" : "否") << endl;
    cout << "2 所在的社交圈大小：" << uf.getCircleSize(2) << endl;
    cout << "5 所在的社交圈大小：" << uf.getCircleSize(5) << endl;

    return 0;
}

在示例代码中，我们创建了一个UnionFind类，包含了并查集的操作。通过unionSets函数可以将两个人所在的社交圈合并，通过areFriends函数可以判断两个人是否为好友，通过getCircleSize函数可以获取某个人所在社交圈的大小。

运行代码会输出以下结果：

Text Only
1
2
3
1 和 4 是否为好友？是
2 所在的社交圈大小：2
5 所在的社交圈大小：3

这说明1和4是好友关系，2所在的社交圈大小为2，5所在的社交圈大小为3。

使用并查集来处理社交网络中的好友关系问题，可以快速判断两个人是否为好友，合并社交圈，并获取每个社交圈的大小。这样可以方便地进行各种社交网络相关的操作和分析。

5、最小生成树算法

在最小生成树算法中，边的选择是通过不同的算法来确定的。两种常见的算法是Prim算法和Kruskal算法。

  1. Prim算法：Prim算法是一种贪心算法，从一个起始节点开始逐步扩展最小生成树。具体步骤如下：
  2. 选择任意一个节点作为起始节点，并将其标记为已访问。
  3. 重复以下步骤，直到所有节点都被访问：
    • 在所有已访问节点的邻接边中，选择权重最小的边。
    • 将该边加入最小生成树，并将边的另一个节点标记为已访问。
  4. Kruskal算法：Kruskal算法也是一种贪心算法，它按照边的权重从小到大进行排序，然后逐个考虑每条边是否加入最小生成树。具体步骤如下：
  5. 对边按照权重从小到大进行排序。
  6. 依次遍历排序后的边，如果当前边的两个端点不在同一个连通分量中，则将该边加入最小生成树，并合并这两个连通分量。

这两种算法都可以用来解决最小生成树问题，但选择哪种算法取决于具体的应用场景和图的特征。

下面是一个使用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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Edge {
    int src;  // 边的起始节点
    int dst;  // 边的目标节点
    int weight;  // 边的权重

    // 构造函数
    Edge(int s, int d, int w) : src(s), dst(d), weight(w) {}
};

// 并查集类
class DisjointSet {
private:
    vector<int> parent;  // 存储每个节点的父节点

public:
    // 构造函数
    DisjointSet(int size) {
        parent.resize(size);

        // 初始化，每个节点的父节点指向自身
        for (int i = 0; i < size; i++) {
            parent[i] = i;
        }
    }

    // 查找根节点（代表元素）
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);  // 路径压缩，将x的父节点直接指向根节点
        }
        return parent[x];
    }

    // 合并两个集合
    void unionSets(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX != rootY) {
            parent[rootX] = rootY;  // 将一个根节点的父节点指向另一个根节点
        }
    }
};

// Kruskal算法求最小生成树
int kruskalMST(vector<Edge>& edges, int numVertices) {
    sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
        return a.weight < b.weight;  // 按边的权重从小到大排序
    });

    DisjointSet ds(numVertices);  // 创建并查集对象

    int minCost = 0;
    for (const auto& edge : edges) {
        int src = edge.src;
        int dst = edge.dst;

        // 判断是否形成环路，如果不形成环路，则将该边加入最小生成树
        if (ds.find(src) != ds.find(dst)) {
            ds.unionSets(src, dst);
            minCost += edge.weight;
        }
    }

    return minCost;
}

int main() {
    int numVertices = 5;  // 图的节点数
    vector<Edge> edges;  // 存储图的边

    // 添加图的边
    edges.push_back(Edge(0, 1, 2));
    edges.push_back(Edge(0, 3, 6));
    edges.push_back(Edge(1, 2, 3));
    edges.push_back(Edge(1, 3, 8));
    edges.push_back(Edge(1, 4, 5));
    edges.push_back(Edge(2, 4, 7));
    edges.push_back(Edge(3, 4, 9));

    // 调用Kruskal算法求解最小生成树
    int minCost = kruskalMST(edges, numVertices);

    cout << "最小生成树的权重和：" << minCost << endl;

    return 0;
}

在示例代码中，我们使用一个结构体Edge来表示图的边，并创建了一个存储边的向量edges。然后调用kruskalMST函数使用Kruskal算法求解最小生成树的权重和。

示例中给定的图包含5个节点和边，每条边都有对应的起始节点、目标节点和权重。运行代码会得到输出结果：最小生成树的权重和：16。这意味着通过Kruskal算法构建的最小生成树权重和为16。

请注意，Kruskal算法使用并查集来判断是否形成环路，以避免在构建最小生成树时出现环路。

6、解决等价关系

并查集是解决等价关系的一种常用算法。下面是使用并查集解决等价关系的示例代码：

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
66
#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

class UnionFind {
private:
    unordered_map<int, int> parent;  // 存储每个节点的父节点
    unordered_map<int, int> size;    // 存储每个集合的大小

public:
    // 查找根节点（代表元素）
    int find(int x) {
        if (parent.find(x) == parent.end()) {
            // 若x不在parent中，说明其为新的集合，将其设置为自身的父节点
            parent[x] = x;
            size[x] = 1;
        }

        if (parent[x] != x) {
            parent[x] = find(parent[x]);  // 路径压缩，将x的父节点直接指向根节点
        }
        return parent[x];
    }

    // 合并两个集合
    void unionSets(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX != rootY) {
            // 将两个集合合并，并更新集合的大小
            parent[rootX] = rootY;
            size[rootY] += size[rootX];
        }
    }

    // 判断两个元素是否等价
    bool areEquivalent(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        return rootX == rootY;
    }

    // 获取集合的大小
    int getSize(int x) {
        int rootX = find(x);
        return size[rootX];
    }
};

int main() {
    UnionFind uf;

    // 添加等价关系
    uf.unionSets(1, 2);
    uf.unionSets(3, 4);
    uf.unionSets(4, 5);

    cout << "1 和 4 是否等价？" << (uf.areEquivalent(1, 4) ? "是" : "否") << endl;
    cout << "2 的集合大小：" << uf.getSize(2) << endl;
    cout << "5 的集合大小：" << uf.getSize(5) << endl;

    return 0;
}

在示例代码中，我们创建了一个UnionFind类来处理等价关系。通过unionSets函数可以将两个元素所在的集合合并，通过areEquivalent函数可以判断两个元素是否等价，通过getSize函数可以获取某个元素所在集合的大小。

运行代码会输出以下结果：

Text Only
1
2
3
1 和 4 是否等价？是
2 的集合大小：2
5 的集合大小：3

这说明1和4是等价的，2所在的集合大小为2，5所在的集合大小为3。

使用并查集来解决等价关系问题，可以快速判断两个元素是否等价，合并集合，并获取每个集合的大小。这样可以方便地进行各种等价关系相关的操作和分析。

7、图像分割问题

并查集也可以用于图像分割问题，其中每个像素点被视为一个节点，而图像中的连接关系被视为边。下面是使用并查集解决图像分割问题的示例代码：

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <iostream>
#include <vector>

using namespace std;

class UnionFind {
private:
    vector<int> parent;  // 存储每个节点的父节点
    vector<int> size;    // 存储每个集合的大小

public:
    // 构造函数
    UnionFind(int n) {
        parent.resize(n);
        size.resize(n, 1);
        // 初始化，每个节点的父节点指向自身
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    // 查找根节点（代表元素）
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);  // 路径压缩，将x的父节点直接指向根节点
        }
        return parent[x];
    }

    // 合并两个集合
    void unionSets(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX != rootY) {
            // 将两个集合合并，并更新集合的大小
            parent[rootX] = rootY;
            size[rootY] += size[rootX];
        }
    }

    // 获取集合的大小
    int getSize(int x) {
        int rootX = find(x);
        return size[rootX];
    }
};

vector<vector<int>> imageSegmentation(vector<vector<int>>& image) {
    int m = image.size();
    int n = image[0].size();

    UnionFind uf(m * n);  // 创建并查集对象

    // 遍历图像的像素点，建立连接关系
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            // 判断当前像素点与其上方和左方像素点的关系
            if (i > 0 && image[i][j] == image[i - 1][j]) {
                uf.unionSets(i * n + j, (i - 1) * n + j);
            }
            if (j > 0 && image[i][j] == image[i][j - 1]) {
                uf.unionSets(i * n + j, i * n + j - 1);
            }
        }
    }

    // 构造分割后的图像
    vector<vector<int>> segmentedImage(m, vector<int>(n));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            int root = uf.find(i * n + j);
            segmentedImage[i][j] = root;
        }
    }

    return segmentedImage;
}

int main() {
    vector<vector<int>> image = {
        {1, 1, 2, 2},
        {1, 3, 3, 2},
        {4, 4, 3, 3}
    };

    vector<vector<int>> segmentedImage = imageSegmentation(image);

    cout << "分割后的图像：" << endl;
    for (auto row : segmentedImage) {
        for (int pixel : row) {
            cout << pixel << " ";
        }
        cout << endl;
    }

    return 0;
}

在示例代码中，我们创建了一个UnionFind类来处理图像分割问题。首先根据图像的大小创建并查集对象uf。然后遍历图像的每个像素点，根据其与上方和左方像素点的关系，通过并查集的unionSets操作建立连接关系。最后构造分割后的图像，将每个像素点的所属集合的代表元素作为该像素点的标记。

运行代码会输出以下结果：

Text Only
1
2
3
4
分割后的图像：
0 0 1 1 
0 2 2 1 
3 3 2 2
本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用