Получение максимального и минимального размера непересекающихся подмножеств

Question

Я пишу код для выполнения Union-Find на графике,

Первая строка ввода:
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/

Answer 1

Ваш подход к использованию несвязного множества верен. Однако вы получаете TLE, потому что ваша сложность O(N*Q) который не пройдет, увидев ограничения. Вы можете оптимизировать свой алгоритм, чтобы получить O(Q*log(N)), Вам в основном нужен максимальный и минимальный размер в любой момент времени. Они будут меняться только во время обновления. Вы можете отслеживать максимальный размер в O(1) просто проверяя после каждого обновления, является ли размер вновь сформированной группы> макс. Для min вы можете использовать BST для хранения значений узлов, упорядоченных по размерам. Лучше использовать C++ STL set, Для каждого выполняемого объединения удалите два узла (я имею в виду родителей, соответствующих узлам запроса) из дерева и вставьте нового родителя с размером. Как происходит вставка и удаление O(logN) время, ваша сложность становится O(QlogN+NlogN) [O(NlogN) построить дерево]