> 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/kruskal-algorithm.md).

# Kruskal Algorithm

## Problem Statement

\
To find MST

## Intuition

```
```

### Links

<https://practice.geeksforgeeks.org/problems/minimum-spanning-tree/1>

### Video Links

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

### Approach 1:

```
```

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

```cpp
class Disjoint{
    vector<int> size,parent;
public:
    Disjoint(int n){
        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(parent[node] == node)
            return node;
            
        return parent[node] = find_ultimate_parent(parent[node]);
    }
    
    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 ;
        
        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];
        }
    }
};


class Solution
{
public:
    int spanningTree(int V, vector<vector<int>> adj[]){
        vector<pair<int, pair<int,int>>> edges;
        
        for(int i=0; i<V; i++){
            for(auto &it: adj[i]){
                int neigh = it[0], wt = it[1];
                edges.push_back({wt,{neigh, i}});
            }
        }
        
        sort(edges.begin(), edges.end());
        int ans = 0;
        Disjoint ds(V);
        for(auto &it: edges){
            int wt = it.first;
            int neigh = it.second.first, node = it.second.second;
            
            if(ds.find_ultimate_parent(neigh) != ds.find_ultimate_parent(node)){
                ans += wt;
                ds.union_by_size(neigh, node);
            }
        }
        
        return ans;

    }
};
```

{% 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

###