Accounts Mergeと連結成分

問題: Accounts Merge

# Example input
accounts = [
    ['John', 'john@mail.com', 'john1@mail.com'],
    ['John', 'john2@mail.com'],
    ['Mary', 'mary@mail.com'],
    ['John', 'john1@mail.com', 'john2@mail.com'],
]
# john@mail.com and john1@mail.com are in account[0]
# john1@mail.com and john2@mail.com are in account[3]
# => john@, john1@, john2@ are all the same person
# Expected output:
# ['John', 'john1@mail.com', 'john2@mail.com', 'john@mail.com']
# ['Mary', 'mary@mail.com']
print('Goal: merge accounts sharing any email into one account')

メールアドレスを整数 ID に対応付ける

accounts = [
    ['John', 'john@mail.com', 'john1@mail.com'],
    ['John', 'john2@mail.com'],
    ['Mary', 'mary@mail.com'],
    ['John', 'john1@mail.com', 'john2@mail.com'],
]

email_to_id = {}
email_to_name = {}
next_id = [0]

for account in accounts:
    name = account[0]
    for email in account[1:]:
        if email not in email_to_id:
            email_to_id[email] = next_id[0]
            next_id[0] += 1
        email_to_name[email] = name

print('Total unique emails:', len(email_to_id))
for email, eid in email_to_id.items():
    print(f'  {email} => id {eid} (owner: {email_to_name[email]})')

各アカウント内のメールアドレスを union する

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    def union(self, x, y):
        self.parent[self.find(x)] = self.find(y)

# After building email_to_id (from previous step)
# email_to_id = {'john@mail.com':0, 'john1@mail.com':1,
#                'john2@mail.com':2, 'mary@mail.com':3}

dsu = DSU(5)  # 4 unique emails

# For account ['John', 'john@mail.com', 'john1@mail.com']:
dsu.union(0, 1)    # john@ and john1@ share account => same component

# For account ['John', 'john1@mail.com', 'john2@mail.com']:
dsu.union(1, 2)    # john1@ and john2@ share account => same component

# Now 0,1,2 all share a root; 3 (mary) is separate
print('find(0)==find(2)?', dsu.find(0) == dsu.find(2))  # True
print('find(0)==find(3)?', dsu.find(0) == dsu.find(3))  # False

連結成分ごとにメールアドレスを集める

from collections import defaultdict

# After DSU unions, group by root
def collect_components(email_to_id, email_to_name, dsu):
    root_to_emails = defaultdict(list)
    for email, eid in email_to_id.items():
        root = dsu.find(eid)
        root_to_emails[root].append(email)

    result = []
    for root, emails in root_to_emails.items():
        # Find the name from any email in this group
        name = email_to_name[emails[0]]
        result.append([name] + sorted(emails))
    return result

# Mock data for illustration
email_to_id = {'john@m.com':0,'john1@m.com':1,'john2@m.com':2,'mary@m.com':3}
email_to_name = {e:'John' for e in list(email_to_id)[:3]}
email_to_name['mary@m.com'] = 'Mary'

class DSU:
    def __init__(self,n): self.p=list(range(n))
    def find(self,x): self.p[x]=self.p[self.p[x]] if self.p[x]!=x else x; return self.p[x] if self.p[x]==x else self.find(self.p[x])
    def union(self,x,y): self.p[self.find(x)]=self.find(y)

dsu=DSU(4); dsu.union(0,1); dsu.union(1,2)
for row in collect_components(email_to_id, email_to_name, dsu):
    print(row)

Accounts Merge の完全な解法

from collections import defaultdict

def accounts_merge(accounts):
    email_to_id = {}
    email_to_name = {}
    eid = 0

    for account in accounts:
        name = account[0]
        for email in account[1:]:
            if email not in email_to_id:
                email_to_id[email] = eid
                eid += 1
            email_to_name[email] = name

    parent = list(range(eid))

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    def union(x, y):
        parent[find(x)] = find(y)

    for account in accounts:
        first_id = email_to_id[account[1]]
        for email in account[2:]:
            union(first_id, email_to_id[email])

    root_to_emails = defaultdict(list)
    for email, i in email_to_id.items():
        root_to_emails[find(i)].append(email)

    return [[email_to_name[emails[0]]] + sorted(emails)
            for emails in root_to_emails.values()]

accounts = [['John','a@m.com','b@m.com'],['John','c@m.com'],
            ['Mary','d@m.com'],['John','b@m.com','c@m.com']]
for row in accounts_merge(accounts):
    print(row)

Accounts Merge の BFS/DFS による代替手法

# BFS alternative (for comparison)
from collections import defaultdict, deque

def accounts_merge_bfs(accounts):
    email_to_accounts = defaultdict(set)
    for i, account in enumerate(accounts):
        for email in account[1:]:
            email_to_accounts[email].add(i)

    visited_accounts = set()
    result = []

    for i, account in enumerate(accounts):
        if i in visited_accounts:
            continue
        queue = deque([i])
        emails_in_group = set()
        while queue:
            acc_idx = queue.popleft()
            if acc_idx in visited_accounts:
                continue
            visited_accounts.add(acc_idx)
            for email in accounts[acc_idx][1:]:
                emails_in_group.add(email)
                for j in email_to_accounts[email]:
                    queue.append(j)
        result.append([account[0]] + sorted(emails_in_group))
    return result

accounts = [['John','a@m.com','b@m.com'],['John','b@m.com','c@m.com'],['Mary','d@m.com']]
for row in accounts_merge_bfs(accounts):
    print(row)

一般化：グラフの連結成分

# Generalised grouping template
def group_equivalents(items, equivalences):
    item_to_id = {item: i for i, item in enumerate(items)}
    n = len(items)
    parent = list(range(n))

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    def union(x, y):
        parent[find(x)] = find(y)

    for a, b in equivalences:
        if a in item_to_id and b in item_to_id:
            union(item_to_id[a], item_to_id[b])

    groups = {}
    for item in items:
        root = find(item_to_id[item])
        groups.setdefault(root, []).append(item)
    return list(groups.values())

# Example: merging duplicate customer records
customers = ['Alice-NY','Alice-LA','Bob','Alice-TX','Carol']
links = [('Alice-NY','Alice-LA'),('Alice-LA','Alice-TX')]
print(group_equivalents(customers, links))

エッジケースへの対応

# Edge case: two Johns with no shared email => separate output
accounts = [
    ['John', 'john_a@m.com'],
    ['John', 'john_b@m.com'],   # different email => different component
    ['Mary'],                    # no emails => skip
]

def accounts_merge_safe(accounts):
    email_to_id = {}; email_to_name = {}; eid = 0
    for account in accounts:
        name = account[0]
        for email in account[1:]:
            if email not in email_to_id:
                email_to_id[email] = eid; eid += 1
            email_to_name[email] = name

    parent = list(range(eid))
    def find(x):
        while parent[x]!=x: parent[x]=parent[parent[x]]; x=parent[x]
        return x
    def union(x,y): parent[find(x)]=find(y)

    for account in accounts:
        if len(account) < 2: continue          # skip no-email accounts
        first = email_to_id[account[1]]
        for email in account[2:]:
            union(first, email_to_id[email])

    from collections import defaultdict
    groups = defaultdict(list)
    for email, i in email_to_id.items():
        groups[find(i)].append(email)
    return [[email_to_name[e[0]]] + sorted(e) for e in groups.values()]

for row in accounts_merge_safe(accounts):
    print(row)

グラフの連結成分の個数

def count_components(n, edges):
    parent = list(range(n))

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    count = n
    for u, v in edges:
        pu, pv = find(u), find(v)
        if pu != pv:
            parent[pu] = pv
            count -= 1
    return count

print(count_components(5, [[0,1],[1,2],[3,4]]))  # 2: {0,1,2} and {3,4}
print(count_components(5, [[0,1],[1,2],[2,3],[3,4]]))  # 1: all connected
print(count_components(5, []))   # 5: no edges, all isolated

最小のコンポーネントと最大のコンポーネント

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py: return
        if self.size[px] < self.size[py]: px, py = py, px
        self.parent[py] = px
        self.size[px] += self.size[py]

def component_stats(n, edges):
    dsu = DSU(n)
    for u, v in edges:
        dsu.union(u, v)
    sizes = [dsu.size[i] for i in range(n) if dsu.find(i) == i]
    print('Component sizes:', sizes)
    print('Largest component:', max(sizes))
    print('Smallest component:', min(sizes))
    print('Number of components:', len(sizes))

component_stats(8, [(0,1),(1,2),(3,4),(5,6),(6,7)])

DSU問題の面接のコツ

# Interview checklist for DSU problems
checklist = [
    '1. Identify: is this a grouping/connectivity/cycle problem?',
    '2. Map problem entities to integer node IDs if needed',
    '3. Implement DSU with path compression + union by rank/size',
    '4. Process all relationships (edges/pairs) with union()',
    '5. Answer queries using find() and size/count tracking',
    '6. Handle edge cases: already connected, single nodes, no edges',
    '7. Check output format: sorted? 1-indexed? Name included?',
    '8. State time complexity: O(n * alpha(n)) ~ O(n)',
]
for item in checklist:
    print(item)

クイックチェック

レッスンのまとめ