> For the complete documentation index, see [llms.txt](https://coding-9.gitbook.io/untitled/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://coding-9.gitbook.io/untitled/graph/mst-disjoint-set/union-by-rank-size.md).

# Union by Rank/ Size

## Problem Statement

\
Find if each two nodes belong to same component

## Intuition

```
```

### Links

### Video Links

<https://www.youtube.com/watch?v=aBxjDBC4M1U&ab_channel=takeUforward>

### Approach 1:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Disjoint{
    vector<int> parent, rank, size;
public:
    Disjoint(int n){
        rank.resize(n+1,0);
        parent.resize(n+1);
        size.resize(n+1,1);

        for(int i=0; i<=n; i++)
            parent[i] = i;
    }  
    
    int find_ultimate_parent(int node){
        if(node == parent[node])
            return node;

        return parent[node] = find_ultimate_parent(parent[node]);
    }

    void union_by_rank(int u, int v){
        int ul_u = find_ultimate_parent(u);
        int ul_v = find_ultimate_parent(v);

        if(ul_u == ul_v)
            return ;
        else if(rank[ul_u] > rank[ul_v]){
            parent[ul_v] = ul_u;
        }
        else if(rank[ul_v] > rank[ul_u]){
            parent[ul_u] = ul_v;
        }
        else{
            parent[ul_v] = ul_u;
            rank[ul_u]++;
        }
    }

    void union_by_size(int u, int v){
        int ul_u = find_ultimate_parent(u);
        int ul_v = find_ultimate_parent(v);

        if(ul_u == ul_v)
            return ;
        else if(size[ul_u] > size[ul_v]){
            parent[ul_v] = ul_u;
            size[ul_u] += size[ul_v];
        }
        else{
            parent[ul_u] = ul_v;
            size[ul_v] += size[ul_u];
        }
    }    
};
```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###