From bf3c1de9f72097bc5a6937344f9402854ce18abc Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Sun, 3 Mar 2019 21:25:10 -0600
Subject: Merging tables done!

Another interesting problem to solve. I gained a much better understanding
of disjoint sets (aka Union/Find) through the coding challenge. A few takeaways:
1. Writing test cases is so important. I can sink my teeth into it and
have something concrete to work on, instead of wasting time beating around the bush;
2. Modify starter code to make it testable, if it's not easy to test to
begin with;
3. Get started early, so I can use my "sleep on it" technique. It really
improves understanding!
4. I'm slightly bothered by the fact that I don't have a test case to catch
the issue with grader test case 8. I looked at the code and added line 61
which enabled me to pass the grader.
---
 src/main/MergingTables.java | 139 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 139 insertions(+)
 create mode 100644 src/main/MergingTables.java

(limited to 'src/main/MergingTables.java')

diff --git a/src/main/MergingTables.java b/src/main/MergingTables.java
new file mode 100644
index 0000000..bf0e337
--- /dev/null
+++ b/src/main/MergingTables.java
@@ -0,0 +1,139 @@
+import java.io.BufferedReader;
+import java.io.IOException;
+import java.io.InputStream;
+import java.io.InputStreamReader;
+import java.io.OutputStream;
+import java.io.PrintWriter;
+import java.util.Locale;
+import java.util.StringTokenizer;
+
+public class MergingTables {
+    private final InputReader reader;
+    private final OutputWriter writer;
+
+    int maximumNumberOfRows = -1;
+    int[] parent;
+    int[] rank;
+    Table[] tables;
+
+    MergingTables(InputReader reader, OutputWriter writer) {
+        this.reader = reader;
+        this.writer = writer;
+    }
+
+    public static void main(String[] args) {
+        InputReader reader = new InputReader(System.in);
+        OutputWriter writer = new OutputWriter(System.out);
+        new MergingTables(reader, writer).run();
+        writer.writer.flush();
+    }
+
+    static class Table {
+        Table setID;
+        int numberOfRows;
+
+        Table(int numberOfRows) {
+            this.numberOfRows = numberOfRows;
+            setID = this;
+        }
+
+    }
+
+    private int find(int i) {
+        if (i != parent[i])
+            parent[i] = find(parent[i]);
+        return parent[i];
+    }
+
+    void merge(int destination, int source) {
+        Table realDestination = tables[find(destination)];
+        Table realSource = tables[find(source)];
+        if (realDestination == realSource) {
+            return;
+        }
+        maximumNumberOfRows = Math.max(maximumNumberOfRows, realDestination.setID.numberOfRows + realSource.setID.numberOfRows);
+        realDestination.numberOfRows = realDestination.setID.numberOfRows + realSource.setID.numberOfRows;
+        realSource.numberOfRows = 0;
+        realSource.setID = realDestination;
+        // The code below fixed the issue with test case 8 from the grader.
+        // My code then passed all tests. I'm slightly bothered that I don't
+        // have a test case to capture it.
+        realDestination.setID = realDestination;
+        union(destination, source);
+    }
+
+    private void union(int destination, int source) {
+        int destination_id = find(destination);
+        int source_id = find(source);
+        if (destination_id == source_id)
+            return;
+        if (rank[destination_id] > rank[source_id])
+            parent[source_id] = destination_id;
+        else {
+            parent[destination_id] = source_id;
+            if (rank[destination_id] == rank[source_id])
+                rank[source_id] = rank[source_id] + 1;
+        }
+    }
+
+    private void run() {
+        int n = reader.nextInt();
+        int m = reader.nextInt();
+        parent = new int[n];
+        rank = new int[n];
+        tables = new Table[n];
+        for (int i = 0; i < n; i++) {
+            int numberOfRows = reader.nextInt();
+            tables[i] = new Table(numberOfRows);
+            parent[i] = i;
+            rank[i] = 0;
+            maximumNumberOfRows = Math.max(maximumNumberOfRows, numberOfRows);
+        }
+        for (int i = 0; i < m; i++) {
+            int destination = reader.nextInt() - 1;
+            int source = reader.nextInt() - 1;
+            merge(destination, source);
+            writer.printf("%d\n", maximumNumberOfRows);
+        }
+    }
+
+
+    static class InputReader {
+        BufferedReader reader;
+        StringTokenizer tokenizer;
+
+        InputReader(InputStream stream) {
+            reader = new BufferedReader(new InputStreamReader(stream), 32768);
+            tokenizer = null;
+        }
+
+        String next() {
+            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
+                try {
+                    tokenizer = new StringTokenizer(reader.readLine());
+                } catch (IOException e) {
+                    throw new RuntimeException(e);
+                }
+            }
+            return tokenizer.nextToken();
+        }
+
+        int nextInt() {
+            return Integer.parseInt(next());
+        }
+
+    }
+
+    static class OutputWriter {
+        PrintWriter writer;
+
+        OutputWriter(OutputStream stream) {
+            writer = new PrintWriter(stream);
+        }
+
+        void printf(String format, Object... args) {
+            writer.print(String.format(Locale.ENGLISH, format, args));
+        }
+    }
+}
+
-- 
cgit v1.2.3