Getting the maximum and minimum size of disjoint subsets

Question

I am writing code to perform Union-Find on a graph,

The first line of input is:
n m [n is number of nodes, and m is number of edges]

Then m lines follow, indicating which two nodes are connected

When I encounter each edge, I perform an union operation, to connect the nodes. After performing the union, I also want to know the size of the largest subset and the smallest subset

This is my code so far,

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

I am using brute-force to get the minimum sized subset and maximum sized subset. This code is getting timed out in Sphere Online Judge.

What would be a more efficient way of getting the minimum sized subset and maximum sized subset.

The SPOJ question link is: http://www.spoj.com/problems/LOSTNSURVIVED/

Answer 1

Your approach of using a disjoint set is right. You are getting a TLE however because your complexity is O(N*Q) which won't pass on seeing the constraints. You can optimise your algorithm to get a O(Q*log(N)). You basically need the max and min size at any point of time. These will change only during an update. You can keep track of the max size in O(1) by simply checking after each update whether the newly formed group's size > max. For min, you can use a BST to store the values of nodes ordered by sizes . Better use C++ STL set . For every union you do, delete the two nodes( I mean the parents corresponding to the query nodes) from the tree and insert the new parent with size. As insertion and deletion takes O(logN) time, your complexity becomes O(QlogN+NlogN) [O(NlogN) to build the tree]