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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
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));
}
}
}
|
