Playground
//koristi C++11 - http://mendo.mk/Lecture.do?id=26 #include <iostream> #include <vector> #include <cstring> #include <algorithm> using namespace std; const int MAX_N = 101; //pochetniot graf int N; vector<pair<int, int> > G[MAX_N]; //union-find int leader[MAX_N]; int ranking[MAX_N]; int Find(int X) { if (leader[X] != X) { int setLeader = Find(leader[X]); leader[X] = setLeader; } return leader[X]; } void Union(int X, int Y) { int setLeaderX = Find(X); int setLeaderY = Find(Y); if (setLeaderX == setLeaderY) { return /* vekje se vo istoto mnozhestvo */; } if (ranking[setLeaderX] == ranking[setLeaderY]) { leader[setLeaderY] = setLeaderX; ranking[setLeaderX]++; } else { if (ranking[setLeaderX] > ranking[setLeaderY]) { leader[setLeaderY] = setLeaderX; } else { leader[setLeaderX] = setLeaderY; } } } //posebna struktura koja ni ovozmozhuva da dodavame rebra vo niza so dinamicka //golemina i da gi podredime so cel izminuvanje vo tochniot redosled struct Edge { int from, to, weight; }; int kruskal() { //inicijaliziraj gi vrednostite vo leader i ranking for (int i=0; i<N; i++) { leader[i] = i; //sekoe teme e vo posebno mnozhestvo } memset(ranking, 0, sizeof(ranking)); //sozdadi lista od site rebra, za da mozheme da gi podredime vector<Edge> edges; for (int i=0; i<N; i++) { for (auto next : G[i]) { Edge edge; edge.from = i; edge.to = next.first; edge.weight = next.second; edges.push_back(edge); } } sort(edges.begin(), edges.end(), [](const Edge a, const Edge b) -> bool { return a.weight < b.weight; }); //izmini gi rebrata (od ona so najmala tezhina, kon ona so najgolema) int totalEdgeWeight = 0; for (auto edge : edges) { if (Find(edge.from) != Find(edge.to)) { //teminjata se vo razlichno mnozhestvo Union(edge.from, edge.to); totalEdgeWeight += edge.weight; } } return totalEdgeWeight; } int main() { N = 5; G[0].push_back({1, 5}); //rebro od 0 do 1, so tezhina 5 G[1].push_back({0, 5}); //grafot e nenasocen, pa dodaj go i obratnoto rebro G[0].push_back({3, 7}); //rebro od 0 do 3 so tezhina 7 G[3].push_back({0, 7}); //grafot e nenasocen, pa dodaj go i obratnoto rebro G[0].push_back({4, 1}); //rebro od 0 do 4 so tezhina 1 G[4].push_back({0, 1}); //grafot e nenasocen, pa dodaj go i obratnoto rebro G[3].push_back({4, 2}); //rebro od 3 do 4 so tezhina 2 G[4].push_back({3, 2}); //grafot e nenasocen, pa dodaj go i obratnoto rebro G[4].push_back({2, 9}); //rebro od 4 do 2 so tezhina 9 G[2].push_back({4, 9}); //grafot e nenasocen, pa dodaj go i obratnoto rebro int result = kruskal(); cout << "Minimum spanning tree has a total weight of " << result << endl; return 0; }
Input data
Program output
Execute
Language: ????????? | Memory: ???? KB | Time: ??? ms
Nothing has been executed, yet!