code. compile. run. debug. share.
Source Code
Language
#include <bits/stdc++.h>
using namespace std;
// DSU data structure
// path compression + rank by union
class DSU
{
int *parent;
int *rank;
public:
DSU (int n)
{
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++)
{
parent[i] = -1;
rank[i] = 1;
}
}
// Find function
int find (int i)
{
if (parent[i] == -1)
{
cout << " Find: i " << i << " parent[i] " << parent[i] << endl;
return i;
}
cout << " Find: i " << i << " parent[i] " << parent[i] << " find. " <<
find (parent[i]) << endl;
return parent[i] = find (parent[i]);
}
// union function
void unite (int x, int y)
{
cout << " Unite x: " << x << " y " << y << endl;
int s1 = find (x);
int s2 = find (y);
cout << " s1 " << s1 << " s2 " << s2 << endl;
if (s1 != s2)
{
cout << "rank[s1] " << rank[s1] << " rank[s2] " << rank[s2] << endl;
if (rank[s1] < rank[s2])
{
parent[s1] = s2;
rank[s2] += rank[s1];
cout << " parent[s1] " << parent[s1] << " rank[s2] " << rank[s2]
<< endl;
}
else
{
parent[s2] = s1;
rank[s1] += rank[s2];
cout << " parent[s2] " << parent[s2] << " rank[s1] " << rank[s1]
<< endl;
}
}
}
};
class Graph
{
vector < vector < int >>edgelist;
int V;
public:
Graph (int V)
{
this->V = V;
}
void addEdge (int x, int y, int w)
{
edgelist.push_back (
{
w, x, y});
}
int kruskals_mst ()
{
// 1. Sort all edges
sort (edgelist.begin (), edgelist.end ());
for (auto edge:edgelist)
{
cout << edge[0] << " " << edge[1] << " " << edge[2] << endl;
}
// Initialize the DSU
DSU s (V);
int ans = 0;
for (auto edge:edgelist)
{
int w = edge[0];
int x = edge[1];
int y = edge[2];
cout << " w " << w << " x " << x << " y " << y << endl;
// take that edge in MST if it does form a cycle
if (s.find (x) != s.find (y))
{
s.unite (x, y);
ans += w;
}
}
cout << ans << endl;
return ans;
}
};
int
main ()
{
Graph g (4);
g.addEdge (0, 1, 1);
g.addEdge (1, 3, 3);
g.addEdge (3, 2, 4);
g.addEdge (2, 0, 2);
g.addEdge (0, 3, 2);
g.addEdge (1, 2, 2);
// int n, m;
// cin >> n >> m;
// Graph g(n);
// for (int i = 0; i < m; i++)
// {
// int x, y, w;
// cin >> x >> y >> w;
// g.addEdge(x, y, w);
// }
cout << g.kruskals_mst ();
return 0;
}
Compiling Program...
Standard Input:
Interactive Console
Text
Program is not being debugged. Click "Debug" button to start program in debug mode.
| # | Function | File:Line |
|---|
| Variable | Value |
|---|
| Register | Value |
|---|
| Expression | Value |
|---|
| # | Description |
|---|