• API
• FAQ
• Tools
• Archive
daily pastebin goal
16%
SHARE
TWEET

Kruskal's algorithm

keverman Feb 13th, 2018 113 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. struct node
2. {
3.     int sz, parent;
4. };
5.
6. struct edge
7. {
8.     int from, to, weight;
9.
10.     edge(int from, int to, int weight)
11.     {
12.         this -> from = from;
13.         this -> to = to;
14.         this -> weight = weight;
15.     }
16. };
17.
18. bool edgeSorter(const edge &lhs, const edge &rhs)
19. {
20.     return lhs.weight > rhs.weight;
21. }
22.
23. int f(int x)
24. {
25.     while(DS[x].parent != x) return DS[x].parent = f(DS[x].parent);
26.     return DS[x].parent;
27. }
28.
29. void unite(int x, int y)
30. {
31.     if(DS[x].parent != DS[y].parent)
32.     {
33.         if(DS[x].sz < DS[y].sz) std::swap(x, y);
34.
35.         DS[y].parent = DS[x].parent;
36.         DS[x].sz += DS[y].sz;
37.         DS[y].sz = 0;
38.     }
39. }
40.
41. std::vector<edge> MST()
42. {
43.     std::sort(edges.begin(), edges.end(), edgeSorter);
44.     std::vector<edge> ret;
45.
46.     for(unsigned int i = 0; i < edges.size(); i++)
47.     {
48.         int u = edges[i].from, v = edges[i].to;
49.
50.         if(f(u) != f(v))
51.         {
52.             ret.push_back(edges[i]);
53.             unite(u, v);
54.         }
55.     }
56.
57.     return ret;
58. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top