721. 账户合并

账户合并

• 难度: medium
• 原始链接: https://leetcode.cn/problems/accounts-merge
• 标签: 并查集, 深度优先遍历

解法一: 并查集

go

func accountsMerge(accounts [][]string) [][]string {
  n := len(accounts)
  unionFind := newUnionFind(n)
  mailGroup := make(map[string]int)
  for i, account := range accounts {
    for _, mail := range account[1:] {
      if groupIndex, ok := mailGroup[mail]; ok {
        unionFind.Union(groupIndex, i)
      } else {
        mailGroup[mail] = i
      }
    }
  }
  groupMail := make(map[int]map[string]bool)
  visit := make([]bool, n)
  for i, account := range accounts {
    if visit[i] {
      continue
    }
    visit[i] = true
    root := unionFind.Find(i)
    if len(groupMail[root]) == 0 {
      groupMail[root] = make(map[string]bool)
    }
    for _, mail := range account[1:] {
      groupMail[root][mail] = true
    }
  }
  ans := make([][]string, 0, len(groupMail))
  for i, mails := range groupMail {
    elements := make([]string, 0, len(mails)+1)
    elements = append(elements, accounts[i][0])
    for mail := range mails {
      elements = append(elements, mail)
    }
    sort.Strings(elements[1:])
    ans = append(ans, elements)
  }
  return ans
}

type UnionFind struct {
  parent []int
}

func newUnionFind(n int) *UnionFind {
  parent := make([]int, n)
  for i := 0; i < n; i++ {
    parent[i] = i
  }
  return &UnionFind{
    parent,
  }
}

func (unionFind *UnionFind) Find(i int) int {
  if unionFind.parent[i] != i {
    unionFind.parent[i] = unionFind.Find(unionFind.parent[i])
  }
  return unionFind.parent[i]
}

func (unionFind *UnionFind) Union(i, j int) bool {
  rootI := unionFind.Find(i)
  rootJ := unionFind.Find(j)
  if rootI == rootJ {
    return false
  }
  unionFind.parent[rootI] = rootJ
  return true
}

解法二: 深度优先遍历

go

func accountsMerge(accounts [][]string) [][]string {
  mails := make(map[string][]int)
  for i, account := range accounts {
    for _, mail := range account[1:] {
      mails[mail] = append(mails[mail], i)
    }
  }
  n := len(accounts)
  visit := make([]bool, n)
  set := make(map[string]bool)
  var dfs func(int)
  dfs = func(i int) {
    if visit[i] {
      return
    }
    visit[i] = true
    for _, mail := range accounts[i][1:] {
      set[mail] = true
      for _, j := range mails[mail] {
        dfs(j)
      }
    }
  }
  ans := [][]string{}
  for i := range n {
    if visit[i] {
      continue
    }
    clear(set)
    dfs(i)
    curMails := make([]string, 0, len(set))
    curMails = append(curMails, accounts[i][0])
    for mail := range set {
      curMails = append(curMails, mail)
    }
    sort.Strings(curMails[1:])
    ans = append(ans, curMails)
  }
  return ans
}