You are viewing a single comment's thread. Return to all comments →
C++ solution:
int parent(int a, std::vector<int>& root) { while(root[a] != a) { root[a] = root[root[a]]; a = root[a]; } return a; } void union_find(int a, int b, std::vector<int>& root) { root[parent(a, root)] = root[parent(b, root)]; } struct edge{ int n1, n2, weight; friend bool operator<(const edge& e1, const edge& e2) { return (e1.weight < e2.weight) or (e1.weight == e2.weight and e1.n1 + e1.n2 + e1.weight < e2.n1 + e2.n2 + e2.weight); } }; int kruskals(int g_nodes, vector<int> g_from, vector<int> g_to, vector<int> g_weight) { std::vector<edge> edges(g_from.size()); for(int i = 0; i < g_from.size(); ++i) edges[i] = edge{g_from[i] - 1, g_to[i] - 1, g_weight[i]}; std::sort(edges.begin(), edges.end()); std::vector<int> root(g_nodes); for(int i = 0; i < g_nodes; ++i) root[i] = i; long price = 0; for(const auto e : edges) { if(parent(e.n1, root) != parent(e.n2, root)) { union_find(e.n1, e.n2, root); price += e.weight; } } return price; }
Seems like cookies are disabled on this browser, please enable them to open this website
Kruskal (MST): Really Special Subtree
You are viewing a single comment's thread. Return to all comments →
C++ solution: