Tirer le maximum et la taille minimale des sous-ensembles disjoints

Question

Je vous écris du code pour effectuer l'Union Trouver sur un graphique,

La première ligne d'entrée est:
nm [n est le nombre de noeuds, et m est nombre d'arêtes]

Ensuite m lignes suivent, ce qui indique que deux noeuds sont connectés

Lorsque je rencontre chaque bord, j'effectuer une opération d'union, pour connecter les noeuds. Après avoir effectué l'union, je veux aussi connaître la taille du plus grand sous-ensemble et le plus petit sous-ensemble

Ceci est mon code jusqu'à présent,

#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; 
} 

J'utilise la force brute pour obtenir le sous-ensemble de taille minimale et sous-ensemble de taille maximale. Ce code est expiré dans Sphère Online Judge.

Ce qui serait un moyen plus efficace d'obtenir le sous-ensemble de taille minimale et le sous-ensemble de taille maximale.

Le lien est question SPOJ: http://www.spoj.com/problems/LOSTNSURVIVED/

Answer 1

Votre approche de l'utilisation d'un ensemble disjoint est juste. Vous obtenez un TLE cependant parce que votre complexité est O(N*Q) qui ne passera pas à voir les contraintes. Vous pouvez optimiser votre algorithme pour obtenir un O(Q*log(N)). Vous avez essentiellement besoin de la taille max et min à tout moment. Cela ne changera que pendant une mise à jour. Vous pouvez suivre la taille maximale dans O(1) en vérifiant simplement après chaque mise à jour si la taille du groupe nouvellement formé> max. Pour min, vous pouvez utiliser un BST pour stocker les valeurs des nœuds classés par tailles. Mieux vaut utiliser C++ STL set. Pour chaque union que vous faites, supprimez les deux nœuds (je veux dire les parents correspondant aux nœuds de requête) de l'arbre et insérez le nouveau parent avec la taille. Comme l'insertion et la suppression prennent O(logN), votre complexité devient O(QlogN+NlogN) [O(NlogN) pour construire l'arbre]