《Email Merge》题目分析

本题直接暴力的做法就是枚举两个用户名，然后比较这两个用户名是否存在相同的邮箱。存在的话就是同一个人：

mark[1 .. N] = false
for i = 1 .. N-1:
    if mark[i]:
        continue
    print username[i] //本组第一个用户名
    for j = i + 1:
        if share-same-email(i, j):
            mark[j] = true
            print username[j] + ' '
    print '\n'

这个算法的复杂度是O(N^2) x O(share-same-email的复杂度)，很有可能超时。

下面我们介绍一个利用倒排索引+并查集的优化算法。

我们知道判断两个字符串A和B是否相等的复杂度是与字符串长度成正比的，要比比较两个整数是否相同的复杂度高。所以首先我们可以做的优化就是把用户名和邮箱都用hashmap映射到整数1, 2, 3 ... 上。这样比较就是O(1)的了。

输入给的数据是每个用户名对应哪些邮箱，我们利用倒排索引可以得到每个邮箱对应哪些用户名：

alice@hihocoder.com: alice
alice@gmail.com: alice alicetest
bob@qq.com: bob
alice@qq.com: alicetest alice2016

注意这里我们为了描述方便使用的还是字符串，实际上你的程序这时处理的应该是映射后的整数。

然后我们使用并查集把有相同邮箱的用户名合并到一个集合。注意由于输入的每个用户名最多10个邮箱，所以这里最多做O(10N)次合并。

最后我们要把所有的集合输出。注意这里还需要花费点代码保证输出顺序与题目要求一致。