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

Question

Я пишу код для выполнения Союз-Найти на графике,

Первая строка ввода является:
нм [п число узлов, и М представляет собой число ребер]

Затем следует м линия, что указует на два узла, которые соединены

Когда я сталкиваюсь каждый край, я выполнить операцию соединения, чтобы соединить узлы. После выполнения объединения, я также хочу знать размер самого большого подмножества и наималейшее подмножество

Это мой код до сих пор,

#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), просто проверяя после каждого обновления, будет ли новый размер группы> макс. В течение мин вы можете использовать BST для хранения значений узлов, упорядоченных по размерам. Лучше использовать C++ STL set. Для каждого объединения вы удаляете два узла (я имею в виду родителей, соответствующих узлам запроса) из дерева, и вставляем новый родитель с размером. Поскольку вставка и удаление занимает O(logN), ваша сложность становится O(QlogN+NlogN) [O(NlogN), чтобы построить дерево]