Unione di account e componenti connesse
Raggruppi gli account che condividono un indirizzo email trattando le email come nodi DSU, quindi raccolga tutte le email di ogni componente per ricostruire gli account uniti.
Unione di account e componenti connesse è una lezione DSA Interview Prep gratuita su CoddyKit. Questa è la lezione 4 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento DSA Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso DSA Interview Prep include 4 lezioni in totale.
Problema: Accounts Merge
Il problema Accounts Merge (LeetCode 721) fornisce un elenco di account, ciascuno dei quali è un elenco di stringhe: il primo elemento è il nome dell'account e i restanti sono indirizzi email. Due account appartengono alla stessa persona se condividono almeno un'email. Occorre unire tutti gli account appartenenti alla stessa persona e restituire gli elenchi di email ordinati.
Si tratta fondamentalmente di un problema di componenti connesse, in cui le email sono i nodi e un account condiviso le collega. DSU è lo strumento ideale: si uniscono tutte le email all'interno dello stesso account e poi si raccolgono le email per componente.
# 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')Mappatura delle email su ID interi
DSU opera su indici interi, mentre i nostri nodi sono stringhe. È necessario mappare ogni email univoca a un ID intero. Occorre inoltre ricordare quale nome è associato a ogni email. Si utilizza un dizionario email_to_id per assegnare ID incrementali e email_to_name per tenere traccia del nome dell'account associato a ogni email.
Ogni email univoca riceve un ID. Se la stessa email compare in più account, viene associata allo stesso ID e l'unione degli ID delle email appartenenti allo stesso account le collega in un'unica componente. Il nome associato all'ID dell'email radice è il nome dell'account unito.
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]})')Unione delle email di ogni account
Per ogni account, si uniscono gli ID di tutte le email elencate insieme. Si sceglie la prima email dell'account come rappresentante e si unisce a essa l'ID di ogni altra email. In questo modo tutte le email dell'account vengono collegate in un'unica componente.
Dopo aver elaborato tutti gli account, le email comparse insieme (direttamente o transitivamente tramite email condivise tra account) condividono tutte la stessa radice DSU. Questo è il passaggio fondamentale che propaga la connettività tra più account.
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)) # FalseRaccolta delle email per componente
Dopo aver completato tutte le unioni, si esegue l'iterazione su ogni email, se ne trova la radice DSU e si raggruppano le email in base a quella radice utilizzando un dizionario di liste. L'ID della radice diventa la chiave. Infine, per ogni gruppo si recupera il nome dell'account, si ordina l'elenco delle email e si antepone il nome.
L'ordinamento delle email è richiesto dal problema: all'interno di un account unito, le email devono essere in ordine lessicografico. Il nome può essere recuperato da una qualsiasi email del gruppo, poiché tutte le email di una componente appartengono alla stessa persona.
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)Soluzione completa di Accounts Merge
Ecco la soluzione completa che combina tutti e tre i passaggi: costruire la mappatura email-ID, unire le email all'interno di ogni account e raccogliere le email raggruppate in base alla radice DSU. La complessità temporale complessiva è O(n × m × alpha(n × m)), dove n è il numero di account e m è il numero massimo di email per account; in pratica è O(n × m).
La complessità spaziale è O(n × m) per le mappe delle email e gli array DSU. La soluzione gestisce correttamente l'unione transitiva: se l'account A condivide l'email X con l'account B e l'account B condivide l'email Y con l'account C, allora A, B e C vengono tutti uniti in un unico gruppo.
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)Alternativa BFS/DFS per l'unione degli account
Un approccio alternativo costruisce un grafo email-account, in cui le email sono nodi e gli archi collegano le email che compaiono nello stesso account. In seguito, BFS/DFS individua ogni componente connessa. Sebbene sia corretto, questo approccio richiede di costruire esplicitamente il grafo e di eseguire BFS a partire da ogni email non ancora visitata: comporta più codice ed è più difficile da analizzare rispetto a DSU.
DSU è più pulito perché la struttura union-find rappresenta naturalmente l'appartenenza alle componenti senza bisogno di una lista di adiacenza esplicita. In questo caso BFS è preferibile solo se occorre ricostruire il percorso o la catena effettiva di email condivise tra due account.
# 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)Generalizzazione: componenti connesse di un grafo
Il modello dell'unione degli account si generalizza a qualsiasi problema di componenti-connesse-con-etichette: si dispone di un insieme di elementi, alcuni dei quali sono dichiarati equivalenti (connessi), e si desidera raggruppare insieme tutti gli elementi transitivamente equivalenti. Tra gli esempi rientrano i problemi di clustering, i gruppi di amici sui social network e il rilevamento di record duplicati.
L'algoritmo generale è sempre il seguente: (1) assegnare un ID intero a ogni elemento, (2) eseguire union sugli ID degli elementi dichiarati equivalenti, (3) raggruppare gli elementi in base alla radice DSU. DSU è essenzialmente un motore di raggruppamento per le relazioni di equivalenza.
# 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))Gestione dei casi limite
Casi limite importanti nell'unione degli account:
- Account con una sola email: un account con una sola email forma una componente propria, a meno che un altro account non condivida quella email.
- Stesso nome, persone diverse: la presenza di «John» in due account non significa che si tratti della stessa persona: solo le email condivise uniscono gli account. Il nome viene memorizzato per email, non per componente.
- Account vuoti: un account senza email deve essere ignorato per evitare errori di indice.
Verifichi sempre che la soluzione gestisca gli account che non devono essere uniti solo perché condividono lo stesso nome. I collegamenti DSU dipendono esclusivamente dagli indirizzi email condivisi.
# 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)Numero di componenti connesse in un grafo
Un problema correlato (LeetCode 323) chiede di calcolare il numero di componenti connesse in un grafo non orientato. È più semplice dell'unione degli account: si inizializza DSU con n nodi, si elaborano tutti gli archi con union e infine si contano le radici distinte.
Il modo più conciso per contare le componenti consiste nel mantenere una variabile count che parte da n e decrementarla ogni volta che un'unione riuscita fonde due componenti diverse. In alternativa, al termine si può contare il numero di nodi i per cui find(i) == i.
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 isolatedComponente più piccola e componente più grande
Una volta disponibile DSU con il tracciamento delle dimensioni, è possibile rispondere a domande come «qual è la dimensione della componente connessa più grande?» o «quante componenti hanno esattamente 3 nodi?» in O(n), scorrendo l'array delle dimensioni in corrispondenza dei nodi radice.
Queste domande compaiono in problemi come «trovare l'isola connessa più grande» su una griglia o «individuare la più piccola partizione della rete». Dopo aver completato tutte le unioni, si cercano i nodi i per cui find(i) == i (le radici) e se ne esaminano le dimensioni.
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)])Suggerimenti per i problemi con DSU
Quando incontra un problema che richiede di unire gruppi, eseguire query di connettività o trovare l'arco aggiuntivo, pensi immediatamente a DSU. Durante i colloqui, citi entrambe le ottimizzazioni (compressione dei percorsi + unione per rango/dimensione) per dimostrare una conoscenza approfondita, anche se un DSU ingenuo e più semplice sarebbe sufficiente con i vincoli dati.
Eviti gli errori più comuni: dimenticare di gestire il caso in cui gli estremi siano già connessi (union non esegue alcuna operazione), usare in modo errato gli indici a partire da 0 o da 1 e non ordinare l'output nell'unione degli account (il problema richiede liste di email ordinate). Chiarisca sempre i vincoli dell'input prima di scrivere il codice.
# 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)Verifica rapida
Verifichi la sua comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep presentati in questa lezione.
Riepilogo della lezione
In questa lezione ha appreso che: l'unione degli account è un problema di componenti connesse in cui le email sono nodi e gli account collegano le email, DSU lo risolve associando alle email ID interi, eseguendo union sugli ID all'interno di ogni account e raggruppando in base alla radice e lo stesso modello di raggruppamento DSU si applica a qualsiasi problema di classi di equivalenza o clustering. Ora si passa alla manipolazione dei bit, iniziando dagli operatori fondamentali AND, OR, XOR, NOT e dagli operatori di shift.
Impara Python con un tutor IA — gratis
Scrivi ed esegui vero codice nel tuo browser, ricevi aiuto istantaneo da un tutor IA disponibile 24/7, e riprendi da dove hai lasciato sul web o nell'app.
- Corsi
- 30
- Lezioni
- 120
Domande Frequenti
La lezione «Unione di account e componenti connesse» è gratuita?
Sì — il testo completo di «Unione di account e componenti connesse» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso DSA Interview Prep, passa a CoddyKit PRO. Il corso DSA Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Unione di account e componenti connesse»?
Raggruppi gli account che condividono un indirizzo email trattando le email come nodi DSU, quindi raccolga tutte le email di ogni componente per ricostruire gli account uniti. Eserciti DSA Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare DSA Interview Prep?
Non è richiesta alcuna esperienza precedente. DSA Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 4 di 4.
Quanto tempo richiede la lezione «Unione di account e componenti connesse»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione DSA Interview Prep?
Sì. Ogni lezione DSA Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- DSU con compressione dei cammini
- Union per rango e limite dell'inversa di Ackermann
- Connessione ridondante e rilevamento dei cicli
- Unione di account e componenti connesse