0

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

输入的第一行是：
nm [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 问题链接是：http ://www.spoj.com/problems/LOSTNSURVIVED/

4

1 回答 1

0

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

于 2016-06-23T07:28:45.670 回答