#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> adj; //邻表
vector<bool> visited;

void dfs(int node, vector<int>& component) 
{
    visited[node] = true;
    component.push_back(node);
    for (int neighbor : adj[node]) {
        if (!visited[neighbor]) {
            dfs(neighbor, component);
        }
    }
}

int main() {
    int n;
    cin >> n;
    adj.resize(n);
    visited.resize(n, false);
    vector<vector<int>> similarity(n, vector<int>(n));

    // 读入相似度矩阵
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            cin >> similarity[i][j];

    // 构建邻接表
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (similarity[i][j] > 0) {
                adj[i].push_back(j);
            }
        }
    }

    vector<int> results;
    
    // 遍历所有节点
    for (int i = 0; i < n; ++i) 
    {
        if (!visited[i]) 
        {
            vector<int> component;
            dfs(i, component);
            // 计算相似度和
            int sum = 0;
            for (int u : component) 
            {
                for (int v : component) 
                {
                    if (similarity[u][v] > 0) 
                    {
                        sum += similarity[u][v];
                    }
                }
            }
            results.push_back(sum / 2); // 每对相似度算两次
        }
    }

    // 输出结果
    sort(results.rbegin(), results.rend());
    for (int sum : results) {
        cout << sum << " ";
    }

    return 0;
}

dfs解法，并不会交并集...

def find(x):
    if parent[x]!=x:
        parent[x] = find(parent[x])
    return parent[x]
n = int(input())
data = [list(map(int,input().split())) for _ in range(n)]
ans = [0]*n
parent = [i for i in range(n)]
for i in range(n):
    for j in range(n):
        if data[i][j]!=0:
            parent_i = find(i)
            parent_j = find(j)
            if parent_i!=parent_j:
                parent[parent_i] = parent_j
for i in range(n):
    for j in range(n):
        parent_i = find(i)
        parent_j = find(j)
        if data[i][j]!=0 and parent_i == parent_j:
            ans[parent_i]+=data[i][j]
            data[i][j]=0
            data[j][i]=0
# num_ans = len(set(find(i) for i in range(n)))
# ans.sort()
# for i in range(n-1,n-num_ans-1,-1):
#     if ans[i]>0:
#         print(ans[i],end=' ')
res = sorted(ans,reverse=True)
for i in range(n):
    if res[i]<=0:
        break
    else:
        print(res[i],end=' ')


            

题面描述:

塔子哥想要对一批图片进行分类，依据它们之间的相似度矩阵进行处理。给定一个$N*N$ 的相似度矩阵，矩阵中的元素表示任意两张图片的相似度，若相似度大于 0，则认为两张图片相似；通过间接相似的方式，形成的相似类会将所有间接相似的图片归为一类。如果某张图片与其他图片均无相似度，则其自成一类。最终，要求输出每个相似类的相似度之和，并按从大到小的顺序排列。

思路

题意需要将相似的图片归为一类，很容易想到是并查集的解法，并查集也有路径压缩的方法，所以可以将相似度的和都存在集合的根节点上。

将所有相似的图片归类到一个集合中，并对图片矩阵$a$进行遍历，如果$a_{i,j}!=0$，那么就获取其所在集合的根节点$fa$，使$ans[fa]+=a[i][j]$。为了防止重复计算，令$a[i][j]=a[j][i]=0$。

最后对$ans$进行排序，再倒序输出即可。

题解

本题的核心在于将相似的图片归为一类，可以使用并查集（Union-Find）数据结构来实现。并查集能够有效地管理并合并集合，使得我们可以快速查找和合并相似的图片。通过路径压缩和按秩合并，查找和合并的效率得到了大幅提升。下面是具体的思路：

1. 初始化并查集：每张图片自成一类，初始化时将每张图片的父节点指向自己。
2. 构建相似度关系：遍历相似度矩阵，如果两张图片的相似度大于 0，则将它们合并到同一个集合中。
3. 计算相似度之和：在合并过程中，我们将相似度的和累加到根节点的相似度和数组中。为了避免重复计算，合并后将对应的相似度值置为 0。
4. 输出结果：最后，对相似度之和进行排序，并输出时按从大到小的顺序。

代码注释解析

1. 数据结构定义：

   • a[1000][1000] 用于存储相似度矩阵。
   • fa[1000] 用于记录每个节点的父节点，构建并查集。
   • ans[1000] 用于存储每个相似类的相似度之和。

2. 路径压缩的查找函数：

   • find(int x) 函数使用路径压缩来提高查找效率。

3. 合并过程：

   • 在读取相似度矩阵时，如果发现相似度不为 0，则合并对应的两张图片。

4. 相似度和的计算：

   • 遍历相似度矩阵，如果两个图片属于同一类，就将其相似度累加到对应的根节点。

5. 结果输出：

   • 对相似度和进行排序，并倒序输出，确保从大到小排列。

代码

C++

#include <bits/stdc++.h>
using namespace std;

int n;                     // 图片数量
int a[1000][1000];        // 相似度矩阵
int fa[1000];             // 并查集的父节点
int ans[1000];            // 每个相似类的相似度之和

// 查找函数，带路径压缩
int find(int x) {
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}

int main() {
    std::ios::sync_with_stdio(false);
    cin >> n;

    // 初始化并查集
    for (int i = 1; i <= n; ++i) {
        fa[i] = i;         // 每个节点的父节点指向自己
    }

    // 读取相似度矩阵并构建并查集
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            cin >> a[i][j];
            if (a[i][j] != 0) {
                int fax = find(i), fay = find(j); // 找到各自的根节点
                if (fax != fay) {
                    fa[fax] = fay;  // 合并两个集合
                }
            }
        }
    }

    // 计算每个相似类的相似度之和
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (a[i][j] && find(i) == find(j)) { // 如果存在相似度并且属于同一类
                ans[find(i)] += a[i][j]; // 将相似度累加到根节点的相似度和中
                a[i][j] = 0;              // 为防止重复计算，将相似度置为0
                a[j][i] = 0;              // 对称位置也置为0
            }
        }
    }

    // 输出相似度之和，先排序
    sort(ans + 1, ans + n + 1);
    for (int i = n; i > 0; --i) { // 倒序输出
        if (ans[i] <= 0) break;   // 只输出正值
        cout << ans[i] << " ";
    }

    return 0;
}

python

# 并查集类定义
class UnionFind:
    def __init__(self, n):
        self.fa = list(range(n + 1))  # 初始化父节点

    def find(self, x):
        if x != self.fa[x]:
            self.fa[x] = self.find(self.fa[x])  # 路径压缩
        return self.fa[x]

def main():
    n = int(input().strip())  # 读取图片数量
    a = [list(map(int, input().strip().split())) for _ in range(n)]  # 读取相似度矩阵
    uf = UnionFind(n)  # 创建并查集实例
    ans = [0] * (n + 1)  # 每个相似类的相似度之和

    # 读取相似度矩阵并构建并查集
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if a[i - 1][j - 1] != 0:  # 注意索引从0开始
                fax = uf.find(i)  # 找到第i个图片的根节点
                fay = uf.find(j)  # 找到第j个图片的根节点
                if fax != fay:
                    uf.fa[fax] = fay  # 合并两个集合

    # 计算每个相似类的相似度之和
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if a[i - 1][j - 1] != 0 and uf.find(i) == uf.find(j):
                ans[uf.find(i)] += a[i - 1][j - 1]  # 将相似度累加到根节点的相似度和中
                a[i - 1][j - 1] = 0  # 为防止重复计算，将相似度置为0
                a[j - 1][i - 1] = 0  # 对称位置也置为0

    # 输出相似度之和，先排序
    sorted_ans = sorted(ans[1:], reverse=True)  # 排序并去掉第0个元素
    for score in sorted_ans:
        if score <= 0:  # 只输出正值
            break
        print(score, end=' ')  # 打印相似度和

if __name__ == "__main__":
    main()