[Leetcode] 721. Accounts Merge

문제 : https://leetcode.com/problems/accounts-merge/

---

accounts 2차원 배열이 주어질 때, accounts[i]의 첫번째 요소가 이름이고 나머지는 이메일이다.

두 계정에 공통 이메일이 있는 경우 두 계정을 합쳐라.

---

Union Find 로 풀었다. 

 

email을 키 값으로 최근에 email을 가진 유저 이름의 인덱스를 저장한다.

만일 탐색중인 이메일에 이미 인덱스가 저장되어 있다면 union 함수로 현재 탐색하는 account 인덱스와 이메일의 최근 인덱스를 합친다.

동일한 이메일을 가지는 account 인덱스끼리 다 합쳤다면 이후엔 동일 부모를 가지는 account들을 합쳐서 정답 배열을 만들어낸다.

 

시간복잡도는 O(NM). N = |accounts|, M = |accounts[i]|

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/721.%20Accounts%20Merge.cpp