diff options
| -rw-r--r-- | src/main/MergingTables.java | 139 | ||||
| -rw-r--r-- | src/test/MergingTablesTest.java | 83 |
2 files changed, 222 insertions, 0 deletions
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)); + } + } +} + diff --git a/src/test/MergingTablesTest.java b/src/test/MergingTablesTest.java new file mode 100644 index 0000000..fcb5829 --- /dev/null +++ b/src/test/MergingTablesTest.java @@ -0,0 +1,83 @@ +import org.junit.jupiter.api.Test; + +import java.io.*; + +import static org.junit.jupiter.api.Assertions.*; + +class MergingTablesTest { + @Test + void test() { + MergingTables.InputReader reader = new MergingTables.InputReader(System.in); + MergingTables.OutputWriter writer = new MergingTables.OutputWriter(System.out); + MergingTables mergingTables = new MergingTables(reader, writer); + mergingTables.tables = new MergingTables.Table[5]; + + MergingTables.Table t0 = new MergingTables.Table(1); + MergingTables.Table t1 = new MergingTables.Table(1); + MergingTables.Table t2 = new MergingTables.Table(1); + MergingTables.Table t3 = new MergingTables.Table(1); + MergingTables.Table t4 = new MergingTables.Table(1); + + mergingTables.tables[0] = t0; + mergingTables.tables[1] = t1; + mergingTables.tables[2] = t2; + mergingTables.tables[3] = t3; + mergingTables.tables[4] = t4; + mergingTables.maximumNumberOfRows = 1; + mergingTables.rank = new int[]{0, 0, 0, 0, 0}; + mergingTables.parent = new int[]{0, 1, 2, 3, 4}; + + mergingTables.merge(2, 4); + assertEquals(2, mergingTables.maximumNumberOfRows); + + mergingTables.merge(1, 3); + assertEquals(2, mergingTables.maximumNumberOfRows); + + mergingTables.merge(0, 3); + assertEquals(3, mergingTables.maximumNumberOfRows); + + mergingTables.merge(4, 3); + assertEquals(5, mergingTables.maximumNumberOfRows); + + mergingTables.merge(4, 2); + assertEquals(5, mergingTables.maximumNumberOfRows); + } + + @Test + void test1() { + MergingTables.InputReader reader = new MergingTables.InputReader(System.in); + MergingTables.OutputWriter writer = new MergingTables.OutputWriter(System.out); + MergingTables mergingTables = new MergingTables(reader, writer); + mergingTables.tables = new MergingTables.Table[6]; + + MergingTables.Table t0 = new MergingTables.Table(10); + MergingTables.Table t1 = new MergingTables.Table(0); + MergingTables.Table t2 = new MergingTables.Table(5); + MergingTables.Table t3 = new MergingTables.Table(0); + MergingTables.Table t4 = new MergingTables.Table(3); + MergingTables.Table t5 = new MergingTables.Table(3); + + mergingTables.tables[0] = t0; + mergingTables.tables[1] = t1; + mergingTables.tables[2] = t2; + mergingTables.tables[3] = t3; + mergingTables.tables[4] = t4; + mergingTables.tables[5] = t5; + mergingTables.maximumNumberOfRows = 10; + mergingTables.rank = new int[]{0, 0, 0, 0, 0, 0}; + mergingTables.parent = new int[]{0, 1, 2, 3, 4, 5}; + + mergingTables.merge(5, 5); + assertEquals(10, mergingTables.maximumNumberOfRows); + + mergingTables.merge(5, 4); + assertEquals(10, mergingTables.maximumNumberOfRows); + + mergingTables.merge(4, 3); + assertEquals(10, mergingTables.maximumNumberOfRows); + + mergingTables.merge(3, 2); + assertEquals(11, mergingTables.maximumNumberOfRows); + } + +}
\ No newline at end of file |