Time Complexity:
1// USACO 2021 US Open Gold Problem 2
2#include <iostream>
3#include <vector>
4#include <algorithm>
5using namespace std;
6void init(int n);
7bool unite(int a, int b);
8
9struct Edge
10{
11 int from, to, cost;
12};
13const int MAX_N = 100000;
14int parent[MAX_N * 2];
15int comp_size[MAX_N * 2];
16int main()
17{
18 int n;
19 cin >> n;
20 init(n * 2);
21 int cost, p1, p2, p3, p4;
22 vector<Edge> edges;
23 for (int i = 0; i < n; i++)
24 {
25 cin >> cost >> p1 >> p2 >> p3 >> p4;
26 // an edge from p1 to p2 or from p3 to p4 has 0 cost
27 edges.push_back({p1 - 1, p2 - 1, 0});
28 edges.push_back({p3 - 1, p4 - 1, 0});
29 // to get an edge from p1 to p3, we need to pay to permute the portals
30 edges.push_back({p1 - 1, p3 - 1, cost});
31 }
32 // sort edges in increasing order of cost
33 sort(edges.begin(), edges.end(), [](Edge a, Edge b){
34 return a.cost < b.cost;
35 });
36 int ans = 0;
37 for (Edge edge : edges)
38 {
39 if (unite(edge.from, edge.to))
40 {
41 ans += edge.cost;
42 }
43 }
44 cout << ans << endl;
45 return 0;
46}
47
48void init(int n)
49{
50 for (int i = 0; i < n; i++)
51 {
52 parent[i] = i;
53 comp_size[i] = 1;
54 }
55}
56
57int find(int a)
58{
59 return a == parent[a] ? a : (parent[a] = find(parent[a]));
60}
61
62bool unite(int a, int b)
63{
64 int root_a = find(a), root_b = find(b);
65 if (root_a == root_b)
66 {
67 return false;
68 }
69 if (comp_size[root_a] > comp_size[root_b])
70 {
71 swap(root_a, root_b);
72 }
73 parent[root_a] = root_b;
74 comp_size[root_b] += comp_size[root_a];
75 return true;
76}Time Complexity:
1// USACO 2021 US Open Gold Problem 2 (using Prim's)
2#include <iostream>
3#include <queue>
4#include <vector>
5using namespace std;
6
7const int MAX_N = 100000;
8struct Node
9{
10 int vertex, cost;
11 bool operator>(Node other) const
12 {
13 return cost > other.cost;
14 }
15};
16int main()
17{
18 int n;
19 cin >> n;
20 priority_queue<Node, vector<Node>, greater<Node>> pq;
21 vector<Node> adj[2 * MAX_N];
22 for (int i = 0; i < n; i++)
23 {
24 int cost, p1, p2, p3, p4;
25 cin >> cost >> p1 >> p2 >> p3 >> p4;
26 p1--; p2--; p3--; p4--;
27 // an edge connecting p1 and p2 or connecting p3 and p4 has cost 0
28 adj[p1].push_back({p2, 0});
29 adj[p2].push_back({p1, 0});
30 adj[p3].push_back({p4, 0});
31 adj[p4].push_back({p3, 0});
32 // to get an edge from p1 to p3, we need to pay to permute the portals
33 adj[p1].push_back({p3, cost});
34 adj[p3].push_back({p1, cost});
35 }
36 pq.push({0, 0});
37 bool visited[2 * MAX_N]{};
38 int ans = 0;
39 // use Prim's to find the MST
40 while (!pq.empty())
41 {
42 int curr = pq.top().vertex, cost = pq.top().cost;
43 pq.pop();
44 if (visited[curr])
45 {
46 continue;
47 }
48 visited[curr] = true;
49 ans += cost;
50 // add edges from the current, visited vertex to unvisited vertices
51 for (Node next : adj[curr])
52 {
53 if (!visited[next.vertex])
54 {
55 pq.push(next);
56 }
57 }
58 }
59 cout << ans << endl;
60 return 0;
61}