Why this matters
A person often has more than one email address and more than one account. A shop may hold one account under a work address and another under a personal address. Later, the same person may sign in with a third address that appears in both. A system that wants one profile per person must work out which accounts belong together. This task is called accounts merge. It is a common interview problem, and it uses union-find in a clear way.
The earlier lesson on union-find builds the structure, and the lesson on union by size and path halving explains why find stays fast. This lesson applies that structure to text. The items are email addresses, not numbers, so the first job is to turn each address into a number. The rest of the work is the same as before.
The problem in plain words
The input is a list of accounts. Each account is a list of strings. The first string is the name on the account. Every string after it is an email address.
Here is a small input:
["John", "johnsmith@mail.com", "john_newyork@mail.com"]
["John", "johnsmith@mail.com", "john00@mail.com"]
["Mary", "mary@mail.com"]
["John", "johnnybravo@mail.com"]Two accounts belong to the same person when they share at least one email address. Here the first two accounts share johnsmith@mail.com, so they are one person. The third account is Mary. The fourth account is a different John, because it shares no address with the others.
The name is not the test. Two accounts can both say John and still be different people. An email address is the test, because a single address is assumed to belong to one person.
The output is one list for each person. Each list starts with the name, then has every email address for that person in sorted order. For the input above, the expected output is:
["John", "john00@mail.com", "john_newyork@mail.com", "johnsmith@mail.com"]
["John", "johnnybravo@mail.com"]
["Mary", "mary@mail.com"]The first John has three addresses, because the two accounts were merged. The second John stands alone. Any order of the lists is correct. This lesson sorts them, so the output is the same on every run.
Why this is a union-find problem
Think of each email address as a node. Each account says: "all of these addresses belong to one person." Saying that for one account means joining all its addresses into one group. That is exactly what a union-find structure does.
Consider the first two accounts. Account 1 joins johnsmith with john_newyork. Account 2 joins johnsmith with john00. After both unions, the three addresses are in one group, even though no single account mentioned all three together. A chain of shared addresses works the same way. If account A shares an address with account B, and B shares one with C, then A, B and C are one person, and union-find joins them without comparing accounts in pairs.
A pairwise approach would compare every account with every other account and check for a shared address. With 1000 accounts that is about half a million comparisons, and each one checks lists of addresses. Union-find does one union per address, plus a short walk for each find. The work stays close to the total number of addresses in the input.
Step 1: give each email a number
Union-find works on numbers 0, 1, 2 and so on. So the first step turns each distinct email address into a number. The number is an id, a label used only inside the program.
The tool for this is std::unordered_map, a C++ table that finds a value by its key in about constant time. Here the key is the email text and the value is the id. When an address is seen for the first time, it gets the next free number. When it is seen again, the table returns the number it already has.
Use try_emplace for this. It inserts the key only when the key is missing, and it tells you whether an insert happened. The program also keeps two vectors. emailOf maps an id back to its address, and nameOf records the name on the first account where that address was seen.
For the first input, step 1 gives these ids, in the order the addresses are first seen:
id 0 = johnsmith@mail.com
id 1 = john_newyork@mail.com
id 2 = john00@mail.com
id 3 = mary@mail.com
id 4 = johnnybravo@mail.comFive distinct addresses appear, so there are five ids. The address johnsmith@mail.com appears twice in the input but gets one id, because the second time the table already has it.
Step 2: union the emails in each account
Once every address has an id, the program walks through the accounts again. For each account, it takes the first address and unites it with every other address in that account. This puts all of the account's addresses into one set.
The first address is a convenient choice of partner. It does not matter which address is picked, because after the unions every address in the account is in the same set. Picking the first keeps the code short.
The structure is the one from the earlier lessons, with union by size and path halving. Here it is written out:
class DisjointSet {
public:
explicit DisjointSet(int n) : parent_(n), size_(n, 1) {
std::iota(parent_.begin(), parent_.end(), 0);
}
int find(int x) {
while (parent_[x] != x) {
parent_[x] = parent_[parent_[x]];
x = parent_[x];
}
return x;
}
void unite(int a, int b) {
int ra = find(a);
int rb = find(b);
if (ra == rb) return;
if (size_[ra] < size_[rb]) std::swap(ra, rb);
parent_[rb] = ra;
size_[ra] += size_[rb];
}
private:
std::vector<int> parent_;
std::vector<int> size_;
};Nothing in this class knows about email addresses. It only knows about ids. That separation is the reason the first step exists.
Step 3: collect each set under its root
After step 2, every address has a root. Two addresses are in the same person's group exactly when their roots are the same number. The next step uses that fact. It goes through all ids, asks for each id's root, and puts the address into a list stored under that root.
The program uses std::map<int, Account>, a sorted table from the root number to the list for that group. Each group list starts with the name. The name is the one stored for the first address in the group, so the code assumes every account in a group has the same name. Real accounts of one person do, but the program does not check it.
Step 4: sort and print
Inside each group, the addresses are sorted with std::sort. The first element of each group list is the name, so the sort starts at the second element with group.begin() + 1. This keeps the name first.
The groups are then sorted by their first address. Each group has its own unique addresses, so this order is always the same. Without this last sort, the output order would follow the root numbers, which depend on how the unions happened, not on the email text.
Here is the full program. It runs the input from the problem, plus two more examples. The second example has no shared addresses, so every account stays separate. The third example is a chain, where one group is built from accounts that link only through each other.
#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>
using Account = std::vector<std::string>;
class DisjointSet {
public:
explicit DisjointSet(int n) : parent_(n), size_(n, 1) {
std::iota(parent_.begin(), parent_.end(), 0);
}
int find(int x) {
while (parent_[x] != x) {
parent_[x] = parent_[parent_[x]];
x = parent_[x];
}
return x;
}
void unite(int a, int b) {
int ra = find(a);
int rb = find(b);
if (ra == rb) return;
if (size_[ra] < size_[rb]) std::swap(ra, rb);
parent_[rb] = ra;
size_[ra] += size_[rb];
}
private:
std::vector<int> parent_;
std::vector<int> size_;
};
std::vector<Account> accountsMerge(const std::vector<Account>& accounts) {
// Step 1: give every distinct email a number, and remember its name.
std::unordered_map<std::string, int> idOf;
std::vector<std::string> emailOf;
std::vector<std::string> nameOf;
for (const Account& account : accounts) {
for (std::size_t i = 1; i < account.size(); ++i) {
const std::string& email = account[i];
int next = static_cast<int>(idOf.size());
auto [it, inserted] = idOf.try_emplace(email, next);
if (inserted) {
emailOf.push_back(email);
nameOf.push_back(account[0]);
}
}
}
// Step 2: every email in one account goes into the same set.
DisjointSet sets(static_cast<int>(emailOf.size()));
for (const Account& account : accounts) {
if (account.size() < 2) continue;
int first = idOf.at(account[1]);
for (std::size_t i = 2; i < account.size(); ++i) {
sets.unite(first, idOf.at(account[i]));
}
}
// Step 3: collect the emails of each set under its root.
std::map<int, Account> groups;
for (int id = 0; id < static_cast<int>(emailOf.size()); ++id) {
int root = sets.find(id);
Account& group = groups[root];
if (group.empty()) group.push_back(nameOf[id]);
group.push_back(emailOf[id]);
}
// Step 4: sort the emails inside each group, then sort the groups by their first email.
std::vector<Account> result;
for (auto& [root, group] : groups) {
std::sort(group.begin() + 1, group.end());
result.push_back(std::move(group));
}
std::sort(result.begin(), result.end(),
[](const Account& a, const Account& b) { return a[1] < b[1]; });
return result;
}
void printAccounts(const std::vector<Account>& accounts) {
for (const Account& account : accounts) {
std::cout << "[";
for (std::size_t i = 0; i < account.size(); ++i) {
if (i > 0) std::cout << ", ";
std::cout << '"' << account[i] << '"';
}
std::cout << "]\n";
}
}
int main() {
std::vector<Account> example1 = {
{"John", "johnsmith@mail.com", "john_newyork@mail.com"},
{"John", "johnsmith@mail.com", "john00@mail.com"},
{"Mary", "mary@mail.com"},
{"John", "johnnybravo@mail.com"},
};
std::cout << "Example 1:\n";
printAccounts(accountsMerge(example1));
std::vector<Account> example2 = {
{"Gabe", "gabe0@m.co", "gabe3@m.co", "gabe1@m.co"},
{"Kevin", "kevin3@m.co", "kevin5@m.co", "kevin0@m.co"},
{"Ethan", "ethan5@m.co", "ethan4@m.co", "ethan0@m.co"},
{"Hanzo", "hanzo3@m.co", "hanzo1@m.co", "hanzo0@m.co"},
{"Fern", "fern5@m.co", "fern1@m.co", "fern0@m.co"},
};
std::cout << "\nExample 2 (no account shares an email):\n";
printAccounts(accountsMerge(example2));
// Accounts 1 to 3 link through a2 and a4, and account 5 links b1 to a1, so one group must chain.
std::vector<Account> example3 = {
{"Ana", "a1@m.co", "a2@m.co"},
{"Ana", "a4@m.co", "a3@m.co"},
{"Ana", "a2@m.co", "a4@m.co"},
{"Ana", "b1@m.co"},
{"Ana", "a1@m.co", "b1@m.co"},
};
std::cout << "\nExample 3 (a chain of shared emails):\n";
printAccounts(accountsMerge(example3));
return 0;
}Compile and run it with:
g++ -std=c++20 -Wall -o accounts accounts.cpp
./accountsThe output is:
Example 1:
["John", "john00@mail.com", "john_newyork@mail.com", "johnsmith@mail.com"]
["John", "johnnybravo@mail.com"]
["Mary", "mary@mail.com"]
Example 2 (no account shares an email):
["Ethan", "ethan0@m.co", "ethan4@m.co", "ethan5@m.co"]
["Fern", "fern0@m.co", "fern1@m.co", "fern5@m.co"]
["Gabe", "gabe0@m.co", "gabe1@m.co", "gabe3@m.co"]
["Hanzo", "hanzo0@m.co", "hanzo1@m.co", "hanzo3@m.co"]
["Kevin", "kevin0@m.co", "kevin3@m.co", "kevin5@m.co"]
Example 3 (a chain of shared emails):
["Ana", "a1@m.co", "a2@m.co", "a3@m.co", "a4@m.co", "b1@m.co"]Example 1 shows the result from the problem. Example 2 shows that the sorting works on its own. Each account has three addresses that are not shared, so nothing merges, and the output lists each one with its addresses in order. Example 3 shows the chain. Accounts 1 and 2 are separate until account 3 links a2 and a4, which sit in different groups. Account 5 then joins b1 to a1. By the end, all of a1 to a4 and b1 are one group. No single account contains all of them.
Worked trace of example 3
The chain is the hardest case, so it is worth following by hand. Here are the ids, in the order the program meets the addresses: a1 gets 0, a2 gets 1, a4 gets 2, a3 gets 3, and b1 gets 4. Each address is then one set on its own.
Account 1 is a1 and a2. The program unites id 0 with id 1. Now {a1, a2} is one set.
Account 2 is a4 and a3. The program unites id 2 with id 3. Now {a4, a3} is another set.
Account 3 is a2 and a4. The first address is a2, with id 1, and the second is a4, with id 2. The root of a2 is in the set {a1, a2}, and the root of a4 is in the set {a4, a3}. These are different sets, so the union joins them into one set with four addresses. This is the step that a single account could not have done alone.
Account 4 has only b1, so there is nothing to unite. It stays a set of one.
Account 5 is a1 and b1. The root of a1 is in the four-address set, and the root of b1 is alone. The union adds b1 to the big set. Now all five addresses are one set.
The last step, step 3, puts every address under the one root. The program then sorts the five addresses and prints one account.
Why the ids come first
A reader might ask why the program does not use the address strings as the nodes of the union-find structure directly. The structure stores its parents in a plain array indexed by number. Using strings would mean hashing a string on every step of find, which is slower. Turning each string into a number once, in step 1, means the structure only ever sees numbers. The cost is one table lookup per address.
The same pattern appears in many problems. When the items are words, cities, user names or web pages, assign each one an integer id, then run the integer algorithm on the ids, and map the answer back to text at the end.
Cost
Let E be the total number of email entries across all accounts, counting repeats. Step 1 looks up each entry once in the table. Step 2 does one unite for each entry after the first in its account, and each unite calls find twice. Step 3 calls find once for each distinct address. With union by size and path halving, each find is close to constant on average, as the earlier lesson showed.
The sorting in step 4 is the main cost that grows faster than the union work. Sorting a group of k addresses costs about k times log k comparisons. For most real inputs the sort is small, because a person has only a few addresses.
Common mistakes
Using the name as the identity. The first attempt of many programmers is to merge accounts that share a name. In example 1, that would merge both Johns into one account, and the output would contain one John with four addresses. The second John, johnnybravo@mail.com, belongs to a different person, and the name does not show that. Merge only on shared addresses.
Looking up an address that was never inserted. Step 2 uses idOf.at(...) to find the id of an address. at assumes the address exists, because step 1 inserted every address in every account. If you skip step 1, or you build the table in a different order, at throws an exception. Here is what a caught exception prints when the code asks for a key that is not in the table:
what(): unordered_map::atThe message is short, so the fix is to find out which key was missing. Usually the table was built from a different input than the one being merged.
Forgetting the first element is the name. Each group list starts with the name. A sort over the whole list would move the name to a random place. The sort must start at group.begin() + 1.
Sorting the groups by their first element before sorting the emails. The groups are sorted by the first email. If the emails inside a group are not sorted yet, the first email is not the smallest one. The code sorts the emails first, then the groups.
Assuming each account has an email. The problem says that every account has at least one address. The code still checks account.size() < 2 and skips such an account, so a name with no address does not crash the program. It also does not appear in the output, which is a choice the code makes, not a rule of the problem.
Checking the output
Two checks catch most mistakes in this program. First, every address from the input must appear in exactly one output account. Count the distinct addresses in the input, which is 5 in example 1, and count the addresses in the output. Both counts must match, and an address that appears twice in the output means a group was split in two. Second, two output accounts must never share an address. If they do, a union was missed.
These checks cost one loop each and do not need the union-find code, so they work as a test on any new input.
Practice
Exercise 1
Here are two accounts: ["A", "x@m", "y@m"] and ["B", "y@m", "z@m"]. Write the merged output, with the name, then the sorted addresses. Say which name the output uses.
Show the answer
["A", "x@m", "y@m", "z@m"]. The two accounts share y@m, so they are one person. The name comes from the first account where the address x@m was seen, which is A. The accounts have different names here, so the output name depends on the order of the input. A real input would give the same name on every account in a group.
Exercise 2
In example 1, how many distinct email addresses are there, and how many ids does step 1 hand out?
Show the answer
Five. The ids are 0 to 4, as the table above shows. The address johnsmith@mail.com appears in two accounts but gets one id.
Exercise 3
In example 2, add the address gabe1@m.co to the end of the Fern account. How many accounts does the output contain, and which name does the merged account use?
Show the answer
Four accounts. The Fern account now shares gabe1@m.co with the Gabe account, so the two merge. The merged account is ["Gabe", "fern0@m.co", "fern1@m.co", "fern5@m.co", "gabe0@m.co", "gabe1@m.co", "gabe3@m.co"]. It is second in the output, because its first address, fern0@m.co, sorts after ethan0@m.co. The name is Gabe because the lowest id in the group is gabe0@m.co, which first appeared on the Gabe account.
Exercise 4
Why does the program sort the groups by their first address and not by their name?
Show the answer
Two different people can have the same name, so the name does not identify a group. Each address belongs to exactly one group, so the first address after sorting is unique to that group. Sorting by it gives a unique, repeatable order.
Exercise 5
A friend says that step 2 could unite every address with every other address in the account, and that this is equally correct. Is the friend right? Explain why, and say what it costs.
Show the answer
Yes, it is correct. Every address in the account ends up in one set either way. It costs more unions. An account with k addresses needs k minus 1 unions when every union uses the first address as partner. Uniting every pair needs k times (k minus 1) divided by 2 unions. The output is the same.
Summary
- Turn each email address into an integer id with a table, then run union-find on the ids.
- Unite the addresses within each account, so one account's addresses share a set.
- Two accounts belong to one person when they share an address, and the name is not used to decide.
- Group the addresses by their root, then sort the addresses in each group and the groups themselves to get a fixed output order.
- A chain of shared addresses needs no special code. Union-find joins the chain as the unions come in.