15,672,088 members
See more:
I was reading Minimum spanning tree - Kruskal with Disjoint Set Union - Competitive Programming Algorithms[^] and I am confused in below operator overloading part used in above implementation,here how we can sort without defining the comparator.

How is sorting taking Place over two structure without defining any comparator,how compiler get to know on what basis it has two sort?
When we are going to use when e1<e2 then who will call the operator overloaded <pre>+</pre>that is e1 or e2.

suppose the default comparator of STL sort using something like this
<pre> e1<e2 </pre> (e1 and e2 are of Edge type) then how are parameters passed to `bool operator<(Edge const& other)` inside struct.

What I have tried:

C++
```struct Edge {
int u, v, weight;
bool operator<(Edge const& other) {
return weight < other.weight;
}
};
vector<Edge> edges;
sort(edges.begin(), edges.end());
```
Posted
Updated 16-Jan-22 22:40pm
v2

## Solution 1

The definition of the `operator <` allows the sort method to compare two `Edge` elements. The `sort` call takes the elements of the vector from first to last, and uses the overloaded comparator as defined in the struct, to decide which order they should be saved in. Because the less than operator is defined for the Edge type, that is the method that will be used when sort does something like:
C++
```if (elem1 < elem2)
{
// ...
}```

CPallini 8-Mar-19 17:41pm
5.

## Solution 2

As an addendum, looking at the documentation std::sort - cppreference.com[^], note the first overload of `std::sort` is used.

## Solution 3

Hello, there is another method to sort vector of edges:
C++
```struct Edge {
int u, v, weight;
};

bool comp(Edge e, Edge f) {
return e.weight < f.weight;
}

vector<Edge> edges;
sort(edges.begin(), edges.end(), comp);```

After you define `struct`, you can use comparison function (`comp`) to let `std::sort` know how to compare your structs.

I hope this is the best solution for your problem, especially in competetive programing.

## Solution 4

And that's already working code for Kruskal algorithm for finding MST (obviously using Disjoint Set Union)

C++
```struct Edge {
int u, v, weight;
};

bool comp(Edge e, Edge f) {
return e.weight < f.weight;
}

vector<Edge> edges;
int n, m, rep[n];

int Find(int v) {
if (rep[v] == v) return v;
return rep[v] = Find(rep[v]);
}

void Union(int u, int v) {
rep[Find(u)] = Find(v);
}

int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) rep[i] = i;
for (int i = 1; i <= m; i++) {
int u, v, weight;
cin >> u >> v >> weight;
edges.push_back({u, v, weight});
}
sort(edges.begin(), edges.end(), comp);
for (Edge e : edges)
if (Find(e.u) != Find(e.v))
Union(e.u, e.v);
}```

Enjoy!