Problem Statement
Given N city and M village where in no villages are connected to the cities. Devise an algorithm that connects all village with roads to cities either direct or indirect route.
Flow of Idea
At first glance, it seemed to be a union-find problem. The cities remain to be primary set and other villages to be unique set that needs to merge. The problem dissolves to simple greedy if we iteratively add the village that has a minimum distance to the primary set. In this case, the locally optimal choice at each stage of choosing a village with minimum distance guaranteed to find the global optimum.
Code
public double determineLength(int[] cityX, int[] cityY, int[] villageX, int[] villageY) {
List<Point> setA = new ArrayList<>();
double result = 0.0;
for (int i = 0; i < cityX.length; i++) // O(N)
setA.add(new Point(cityX[i], cityY[i]));
boolean[] visited = new boolean[villageX.length];
for (int i = 0; i < villageX.length; i++) {
double min_dist = Double.MAX_VALUE;
int variable = -1;
for (int j = 0; j < villageX.length; j++) {
if (visited[j]) continue;
for (int k = 0; k < setA.size(); k++) {
double aux_dist = euclidean(setA.get(k), villageX[j], villageY[j]);
if (aux_dist < min_dist) {
variable = j;
min_dist = aux_dist;
}
}
}
result += min_dist;
setA.add(new Point(villageX[variable], villageY[variable]));
visited[variable] = true;
}
return result;
}
private double euclidean(Point point, int x, int y) {
double x1 = point.getA() - x;
double y1 = point.getB() - y;
return Math.sqrt(x1 * x1 + y1 * y1);
}