Approach
Map each person’s name to a parent name, and keep a component size for each root. Initially, every newly encountered name is its own root with size one. For a friendship, find both roots and link the smaller component under the larger one, adding their sizes at the surviving root. If the roots are already equal, nothing changes; print that root’s existing size regardless. A fresh disjoint-set structure is created for each test case.
The invariant is that every name in a connected friendship group reaches the same root, and the size stored at that root equals the number of people in the group. Path compression preserves the root while shortening future searches; union by size prevents tall trees. Both operations together take amortized O(α(V)) time per friendship, where V is the number of distinct names in the case; including expected constant-time hash-map access, all F friendships take expected O(F α(V)) time. The maps use O(V) space. find is iterative, so even an unusually deep parent chain cannot exhaust the call stack.
Java
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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
FastScanner input = new FastScanner();
int testCases = input.nextInt();
StringBuilder output = new StringBuilder();
for (int testCase = 0; testCase < testCases; testCase++) {
int friendshipCount = input.nextInt();
DisjointSet friends = new DisjointSet();
for (int i = 0; i < friendshipCount; i++) {
String first = input.next();
String second = input.next();
output.append(friends.union(first, second)).append('\n');
}
}
System.out.print(output);
}
private static class DisjointSet {
private final Map<String, String> parent = new HashMap<>();
private final Map<String, Integer> size = new HashMap<>();
private void add(String name) {
if (!parent.containsKey(name)) {
parent.put(name, name);
size.put(name, 1);
}
}
private String find(String name) {
String root = name;
while (!parent.get(root).equals(root)) {
root = parent.get(root);
}
while (!name.equals(root)) {
String next = parent.get(name);
parent.put(name, root);
name = next;
}
return root;
}
int union(String first, String second) {
add(first);
add(second);
String firstRoot = find(first);
String secondRoot = find(second);
if (firstRoot.equals(secondRoot)) {
return size.get(firstRoot);
}
if (size.get(firstRoot) < size.get(secondRoot)) {
String temporary = firstRoot;
firstRoot = secondRoot;
secondRoot = temporary;
}
parent.put(secondRoot, firstRoot);
int combinedSize = size.get(firstRoot) + size.get(secondRoot);
size.put(firstRoot, combinedSize);
size.remove(secondRoot);
return combinedSize;
}
}
private static class FastScanner {
private final BufferedReader reader = new BufferedReader(
new InputStreamReader(System.in));
private StringTokenizer tokenizer;
String next() throws IOException {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
tokenizer = new StringTokenizer(reader.readLine());
}
return tokenizer.nextToken();
}
int nextInt() throws IOException {
return Integer.parseInt(next());
}
}
}