forked from fineanmol/Hacktoberfest2024
-
Notifications
You must be signed in to change notification settings - Fork 30
/
Minimize rope length to connect given points in a 3D plane
77 lines (70 loc) · 1.51 KB
/
Minimize rope length to connect given points in a 3D plane
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
// C++ code for the above approach:
#include <bits/stdc++.h>
using namespace std;
vector<vector<int> > edges;
int findparent(int a, vector<int>& parentOf)
{
if (parentOf[a] == -1)
return a;
return parentOf[a] = findparent(parentOf[a], parentOf);
}
void union_set(int a, int b, vector<int>& parentOf,
vector<int>& rank)
{
int s1 = findparent(a, parentOf);
int s2 = findparent(b, parentOf);
if (s1 != s2) {
int r1 = rank[s1];
int r2 = rank[s2];
if (r1 >= r2) {
parentOf[s2] = s1;
rank[s1] = r1 + r2;
}
else {
parentOf[s1] = s2;
rank[s2] = r1 + r2;
}
}
}
int calculatemst(int N)
{
int cost = 0;
vector<int> rank(N + 1, -1);
vector<int> parentOf(N + 1, -1);
for (int i = 0; i < edges.size(); i++) {
int wt = edges[i][0], a = edges[i][1],
b = edges[i][2];
if (findparent(a, parentOf)
!= findparent(b, parentOf)) {
cost += wt;
union_set(a, b, parentOf, rank);
}
}
return cost;
}
void graph(vector<pair<int, int> > v)
{
for (int i = 0; i < v.size() - 1; i++) {
int dist = v[i + 1].first - v[i].first;
int nodeone = v[i].second;
int nodesecond = v[i + 1].second;
edges.push_back({ dist, nodeone, nodesecond });
}
}
void solve(int a[][3], int N)
{
vector<pair<int, int> > x, y, z;
for (int i = 0; i < N; i++) {
x.push_back({ a[i][0], i + 1 });
y.push_back({ a[i][1], i + 1 });
z.push_back({ a[i][2], i + 1 });
}
sort(x.begin(), x.end());
sort(y.begin(), y.end());
sort(z.begin(), z.end());
graph(x);
graph(y);
graph(z);
sort(edges.begin(), edges.end());
return;
}