Editing 2016 Dec Gold Problem 1 Moocast (section)

== Code (Union Find) ==

=== C++ ===
<pre>
#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int i, j, w;
    bool operator<(const Edge& other) const {
        return w < other.w;
    }
};

vector<int> parent;

int find(int curr) {
    return parent[curr] == curr ? curr : (parent[curr] = find(parent[curr]));
}

void merge(int x, int y) {
    parent[find(x)] = find(y);
}

int main() {
    ifstream fin("moocast.in");
    ofstream fout("moocast.out");

    int n;
    fin >> n;
    vector<int> x(n), y(n);
    for (int i = 0; i < n; i++) {
        fin >> x[i] >> y[i];
    }

    parent.resize(n);
    vector<Edge> edges;
    for (int i = 0; i < n; i++) {
        parent[i] = i;
        for (int j = 0; j < i; j++) {
            int distance = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]);
            edges.push_back({i, j, distance});
        }
    }

    sort(edges.begin(), edges.end());
    int lastWeight = 0;
    int numComponents = n;
    for (const Edge& curr : edges) {
        if (find(curr.i) != find(curr.j)) {
            merge(curr.i, curr.j);
            lastWeight = curr.w;
            if (--numComponents == 1) {
                break;
            }
        }
    }

    fout << lastWeight << endl;
    fout.close();
}

</pre>

=== Java ===
<pre>
import java.io.*;
import java.util.*;

public class MooCast {
    static class Edge implements Comparable<Edge> {
        int i, j, w;

        public Edge(int i, int j, int w) {
            this.i = i;
            this.j = j;
            this.w = w;
        }

        @Override
        public int compareTo(Edge other) {
            return this.w - other.w;
        }
    }

    static int[] parent;

    public static int find(int curr) {
        return parent[curr] == curr ? curr : (parent[curr] = find(parent[curr]));
    }

    public static void merge(int x, int y) {
        parent[find(x)] = find(y);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new FileReader("moocast.in"));
        PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("moocast.out")));
        int n = Integer.parseInt(br.readLine());
        int[] x = new int[n];
        int[] y = new int[n];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            x[i] = Integer.parseInt(st.nextToken());
            y[i] = Integer.parseInt(st.nextToken());
        }
        parent = new int[n];
        ArrayList<Edge> edges = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            for (int j = 0; j < i; j++) {
                int distance = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]);
                edges.add(new Edge(i, j, distance));
            }
        }
        Collections.sort(edges);
        int lastWeight = 0;
        int numComponents = n;
        for (Edge curr : edges) {
            if (find(curr.i) != find(curr.j)) {
                merge(curr.i, curr.j);
                lastWeight = curr.w;
                if (--numComponents == 1) {
                    break;
                }
            }
        }
        pw.println(lastWeight);
        pw.close();
    }
}

</pre>

=== Python ===
<pre>
from sys import stdin
import heapq

def find(curr):
    global parent
    return curr if parent[curr] == curr else find(parent[curr])

def merge(x, y):
    global parent
    parent[find(x)] = find(y)

def main():
    with open("moocast.in", "r") as fin:
        n = int(fin.readline().strip())
        coords = [tuple(map(int, fin.readline().split())) for _ in range(n)]

    parent = list(range(n))
    edges = []

    for i in range(n):
        for j in range(i):
            x1, y1 = coords[i]
            x2, y2 = coords[j]
            distance = (x1 - x2) ** 2 + (y1 - y2) ** 2
            heapq.heappush(edges, (distance, i, j))

    last_weight = 0
    num_components = n

    while num_components > 1:
        weight, i, j = heapq.heappop(edges)
        if find(i) != find(j):
            merge(i, j)
            last_weight = weight
            num_components -= 1

    with open("moocast.out", "w") as fout:
        fout.write(str(last_weight) + "\n")

if __name__ == "__main__":
    main()

</pre>

[[Category:Yearly_2016_2017]]
[[Category:Gold]]
[[Category:Depth-First Search]]
[[Category:Breadth-First Search]]
[[Category:Graph]]
[[Category:Binary Search]]
[[Category:Search]]
[[Category:Union Find]]
[[Category:Flood Fill]]
[[Category:Union-Find]]
[[Category:DFS]]