# Untitled

unknown
plain_text
15 days ago
2.2 kB
1
Indexable
Never
```#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

#define edge pair<int, int>

class Graph {
private:
//int is weight here
vector<pair<int, edge>> G; //Graph
vector<pair<int, edge>> T; //MST
int* parent;
int V; // number of vertices/nodes in graph
public:
Graph(int V);
//u is vertex one and v is vertex two and weight is w
void AddWeightedEdge(int u, int v, int w);
int find_set(int i);
void union_set(int u, int v);
void kruskal();
void print();
};

Graph::Graph(int V) {
parent = new int[V];

//i 0 1 2 3 4 5
//parent[i] 0 1 2 3 4 5
for (int i = 0; i < V; i++)
parent[i] = i;

G.clear();
T.clear();
}

void Graph::AddWeightedEdge(int u, int v, int w) {
G.push_back(make_pair(w, edge(u, v)));
}

//find parent
int Graph::find_set(int i) {
// If i is the parent of itself
if (i == parent[i])
return i;
else
//Else if i is not the parent of itself
//Then i is not the representative of his set,
//so we recursively call Find on its parent
return find_set(parent[i]);
}

void Graph::union_set(int u, int v) {
parent[u] = parent[v];
}

void Graph::kruskal() {
int i, uParent, vParent;
sort(G.begin(), G.end()); //increasing weight
for (i = 0; i < G.size(); i++) {
uParent = find_set(G[i].second.first);
vParent = find_set(G[i].second.second);
if (uParent != vParent) {
union_set(uParent, vParent);
}
}
}

void Graph::print() {
cout << "Edge :"
<< " Weight" << endl;
for (int i = 0; i < T.size(); i++) {
cout << T[i].second.first << " - " << T[i].second.second << " : "
<< T[i].first;
cout << endl;
}
}

int main() {
Graph g(9);