Linux并行版数量
#并查集 2025-03-30 
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
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

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

// 并查集 - 按大小合并，这是题目本身所要求的
void merge(int x, int y, vector<int>& dp) {
	int x_root = find(dp, x);
	int y_root = find(dp, y);
	auto min_root = min(x_root, y_root);
	dp[x_root] = min_root;
	dp[y_root] = min_root;
}

int main() {
    int n;
    cin >> n;

    vector<vector<int>> ans(n, vector<int>(n));
    vector<int> dp(n);

    for (int i = 0; i < n; i++) {
        dp[i] = i;
    }

    // 读取邻接矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> ans[i][j];
        }
    }

    // 仅遍历左下三角部分 (i > j)
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (ans[i][j]) {
                merge(i, j, dp);
            }
        }
    }

    // 计算最大连通块大小
    int res = 0;
    map<int, int> mp;
    for (int i = 0; i < n; i++) {
        int root = find(dp, i);
        mp[root]++;
        res = max(res, mp[root]);
    }

    cout << res;

    return 0;
}
复制代码

并查集的合并

并查集的路径压缩写法是固定的，但是合并两个集合就不一定，往往要根据题意来看。

题目说：这些发行版互相存在关联，例如 Ubuntu 基于 Debian 开发，而 Mint 又基于 Ubuntu 开发，那么我们认为 Mint 同 Debian 也存在关联。

可以看出，有某个系统基于某个系统开发的描述，也就是说高版本应该合并到低版本上，因为高版本基于低版本开发。

1
2
3
4
5
6
7
void merge(int x, int y, vector<int>& dp) {
	int x_root = find(dp, x);
	int y_root = find(dp, y);
	auto min_root = min(x_root, y_root);
	dp[x_root] = min_root;
	dp[y_root] = min_root;
}
复制代码

为什么只处理对称的数据

1
2
3
4
1 1 0 0
1 1 1 0
0 1 1 0
0 0 0 1
复制代码

题目描述是：isConnected[i][j] = 1 表示第 i 个发行版和第 j 个发行版直接关联，而 isConnected[i][j] = 0 表示二者不直接相连。

那我把下标标出：

image20250330201408511.png