721.账户合并

并查集

注意使用Hashmap来存储邮箱和父节点邮箱。

时间复杂度： O(NlogN)
空间复杂度： O(N)

func accountsMerge(accounts [][]string) [][]string {

    ans := [][]string{}
    email_to_name := make(map[string]string)
    emails_list := make(map[string]string)

	// 查找
    var find func(string) string
    find = func(email string) string{
        if emails_list[email] == email {
            return email
        }

        emails_list[email] = find(emails_list[email])
        return emails_list[email]
    }

	// 合并
    union := func(email1 string,  email2 string) {
        e1 := find(email1)
        e2 := find(email2)

        // fmt.Printf("union: %v, %v\n", email1, email2)
        emails_list[e1] = e2
    }
    
    for _, account := range accounts {
        name := account[0]
        emails := account[1:]

        for i, email := range emails {
            if i == 0 {
                email_to_name[email] = name
            }
            // 没出现过的邮箱关联父节点到当前账号的首个邮箱
            if _, ok := emails_list[email]; !ok {
                emails_list[email] = emails[0]
            } else {
            // 出现过的邮箱则把当前账号和出现过的账号合并
                union(emails[0], email)
            }
        }
    }

    group := make(map[string][]string)
    for email, fa := range emails_list {
	    // 获取邮箱的真实父节点邮箱
        fa = find(fa)
        if _, ok := group[fa]; ok {
            group[fa] = append(group[fa], email)
        } else {
            group[fa] = []string{email}
        }
    }

    for fa, emails := range group {
        sort.Strings(emails)
        ans = append(ans, append([]string{email_to_name[fa]}, emails...))
    }

    // fmt.Printf("group: %v", group)
    

    return ans
}