获取不相交子集的最大和最小大小

Question

我正在编写代码以在图上执行联合查找，

第一行输入为：
n m [n为节点数，m为边数]

然后m行，表示连接了哪两个节点

当我遇到每条边时，我执行并集操作来连接节点。执行并集后，我还想知道最大子集和最小子集的大小

到目前为止，这是我的代码，

#include <iostream>
using namespace std;

int arr[100001];
int size[100001];

void initialize(int n){
    for(int i=1; i<=n; i++){
        arr[i] = i;
        size[i] = 1;
    }
}

int root(int a){
    while(arr[a] != a){
        //Path compression
        arr[a] = arr[arr[a]];
        a = arr[a];
    }
    return a;
}

void weighted_union(int a, int b){
    int root_a = root(a);
    int root_b = root(b);
    //Perform union, if the two elements are not already in the same subset
    if(root(a) != root(b)){
        if(size[root_a] < size[root_b]){
            arr[root_a] = root_b;
            size[root_b] += size[root_a];
        }
        else{
            arr[root_b] = root_a;
            size[root_a] += size[root_b];
        }
    }
}

void print_result(int n){
    int max_size = 1;
    int min_size = 100000;
    for(int i=1; i<=n; i++){
        //If it's a root node, then check the size
        if(arr[i] == i){
            if(size[i] > max_size){
                max_size = size[i];
            }
            if(size[i] < min_size){
                min_size = size[i];
            }
        }
    }
    cout<<max_size - min_size<<endl;
}

int main() {
    //For fast IO
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n,m,a,b;
    cin>>n>>m;
    initialize(n);
    for(int edge=0; edge<m; edge++){
        cin>>a>>b;
        weighted_union(a,b);
        print_result(n);
    }
    return 0;
}

我正在使用暴力获取最小大小的子集和最大大小的子集。此代码在 Sphere Online Judge 中超时。

获取最小大小子集和最大大小子集的更有效方法是什么。

SPOJ 问题 link 是：http://www.spoj.com/problems/LOSTNSURVIVED/

Answer 1

您使用不相交集的方法是正确的。但是，您得到的是 TLE，因为您的复杂性是 O(N*Q)，它不会通过查看约束。您可以优化算法以获得 O(Q*log(N))。您基本上在任何时候都需要最大和最小尺寸。这些只会在更新期间更改。您可以通过在每次更新后检查新形成的组的大小是否 > 最大值来跟踪 O(1) 中的最大大小。对于 min，您可以使用 BST 来存储按 sizes 排序的节点值。最好使用 C++ STL set 。对于您执行的每个联合，从树中删除两个节点（我的意思是对应于查询节点的父节点）并插入具有大小的新父节点。由于插入和删除需要 O(logN) 时间，因此您的复杂性变为 O(QlogN+NlogN) [O(NlogN) 来构建树]

获取不相交子集的最大和最小大小

Getting the maximum and minimum size of disjoint subsets

disjoint-sets

disjoint-union