相似图片分类-并查集

#include <bits/stdc++.h>

using namespace std;

const int N = 910;

int n, p[N], num[N], a[N][N];

int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++) p[i] = i, num[i] = 0;
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < n; j ++)
            cin >> a[i][j];
    for(int i = 0; i < n; i ++)
        for(int j = i; j < n; j ++)
        {
            if(a[i][j] > 0)
            {
                int px = find(i), py = find(j);
                if(px != py)
                {
                    p[px] = py;
                    num[py] += a[i][j] + num[px];
                }
                else
                {
                    num[py] += a[i][j];
                }
            }
        }
    vector<int> res;
    for(int i = 0; i < n; i ++)
    {
        if(p[i] == i)
        {
            res.push_back(num[i]);
        }
    }
    sort(res.begin(), res.end());
    for(int i = res.size() - 1; i >= 0; i --)
    {
        if(i) cout << res[i] << " ";
        else cout << res[i];
    }
    return 0;
}