Number of Provinces
Il y a n villes, numérotées de 0 à n-1. isConnected[i][j] vaut 1 lorsqu’une route relie directement la ville i et la ville j, et 0 dans le cas contraire. Les routes sont à double sens, donc la matrice est symétrique, et chaque ville est reliée à elle-même.
Une province est un groupe de villes qui peuvent toutes se rejoindre, directement ou en passant par d’autres villes, sans qu’aucune route ne mène à l’extérieur du groupe. Retourne le nombre de provinces.
Fonction
- isConnectedinteger-2d-array
- la matrice n × n, 1 lorsqu’une route relie directement deux villes
- Renvoieinteger
- le nombre de provinces
Contraintes
1 ≤ n ≤ 150, oùn = isConnected.lengthisConnected[i].length = nisConnected[i][j]vaut0ou1isConnected[i][i] = 1isConnected[i][j] = isConnected[j][i]
Exemples
- Entrée
- isConnected = [[1, 0, 0, 1], [0, 1, 1, 0], [0, 1, 1, 0], [1, 0, 0, 1]]
- Sortie
- 2
- Explication
- La ville 0 a une route vers la ville 3, et la ville 1 a une route vers la ville 2. Aucune route ne relie les deux paires, il y a donc 2 provinces.
- Entrée
- isConnected = [[1, 1, 0, 0, 0], [1, 1, 1, 0, 0], [0, 1, 1, 0, 0], [0, 0, 0, 1, 0], [0, 0, 0, 0, 1]]
- Sortie
- 3
- Explication
- Les villes 0 et 2 n’ont pas de route directe, mais toutes deux sont reliées à la ville 1 ; les villes 0, 1 et 2 forment donc une province. Les villes 3 et 4 n’ont pas de routes et constituent chacune une province : il y en a 3 au total.
Pour aller plus loin
Chaque route s’ouvre désormais un jour donné. Peux-tu trouver le premier jour où toutes les villes appartiennent à une même province ?
Indices
Ouvrez-les un par un. Chacun en dévoile un peu plus.
Représente chaque ville par un point et chaque
1hors de la diagonale par une ligne entre deux points. À quoi ressemble une province sur cette représentation ?Une province est une composante connexe : un 0 entre deux villes ne signifie pas qu’elles sont séparées, car une troisième ville peut les relier. Compte le nombre de fois où tu dois lancer une nouvelle recherche depuis une ville qu’aucune recherche précédente n’a atteinte.
Autre méthode : commencez avec
ngroupes, un par ville, et fusionnez les groupes deietjpour chaque 1 au-dessus de la diagonale. La fusion de deux groupes différents réduit le compte de un. Une structure union-find avec compression de chemin rend chaque fusion presque constante en temps.
Solution
La matrice décrit un graphe non orienté : les villes sont des nœuds et chaque 1 est une arête. Une province est une composante connexe, et un 0 entre deux villes ne les sépare pas lorsqu’une troisième ville les relie toutes les deux. Une recherche depuis chaque ville non visitée, ou une structure union-find appliquée à chaque arête, compte les composantes en O(n²).
Recherche en profondeur depuis chaque ville non visitée
Intuition
Une ville non marquée ne peut pas appartenir à une province que tu as déjà comptée, car chaque recherche marque toute sa province. Elle en commence donc une nouvelle. La recherche suit les lignes de la matrice : dans le deuxième exemple, la recherche depuis la ville 0 atteint la ville 1, puis la ligne de la ville 1 atteint la ville 2, même si la ligne 0 contient un 0 pour la ville 2.
Chaque ville est retirée de la pile une fois et lit sa ligne de n entrées, donc tu lis la matrice une fois : O(n²) en temps. Les marques et la pile contiennent au plus n villes, donc l’espace supplémentaire est O(n).
Algorithme
- Créez un indicateur de visite pour chaque ville et définissez le compteur à 0.
- Parcourez les villes dans l’ordre et ignorez celles déjà visitées.
- Pour une ville non visitée, ajoutez 1 au compteur, marquez-la comme visitée et empilez-la.
- Tant que la pile contient des villes, dépilez-en une et empilez chaque ville de sa ligne qui a une valeur de 1 et qui n’a pas encore été visitée, en la marquant au moment de l’empiler.
- Renvoyez le compteur.
def findCircleNum(isConnected):
n = len(isConnected)
seen = [False] * n
provinces = 0
for start in range(n):
if seen[start]:
continue
# Nobody reached this city from an earlier province, so it starts a new one.
provinces += 1
seen[start] = True
stack = [start]
while stack:
city = stack.pop()
row = isConnected[city]
for other in range(n):
# Mark a city when you push it, so it is never pushed twice.
if row[other] == 1 and not seen[other]:
seen[other] = True
stack.append(other)
return provincesUnion-find avec compression de chemin et union par rang
Intuition
Commencez avec n provinces, une par ville. Chaque 1 au-dessus de la diagonale indique que deux villes doivent être regroupées : si leurs groupes diffèrent, fusionnez-les et diminuez le nombre de un. Dans le deuxième exemple, le nombre commence à 5, (0, 1) fusionne les villes 0 et 1, (1, 2) ajoute la ville 2 à leur groupe, et il reste 3 provinces.
Union-find stocke chaque groupe sous forme d’arbre : parent[c] pointe d’un niveau vers le haut, et deux villes appartiennent au même groupe lorsque find les mène toutes deux à la même racine. Si on les laisse seules, les fusions peuvent former un long chemin que chaque find parcourt en O(n) étapes. L’union par rang place l’arbre le plus court sous le plus grand, de sorte qu’aucun chemin ne dépasse log n. La compression de chemin fait pointer directement vers la racine chaque ville traversée par find. Ensemble, ces techniques rendent chaque find amorti en O(α(n)), et α(n) est au plus égal à 4 en pratique.
Algorithme
- Définissez
parent[c] = cetrank[c] = 0pour chaque ville, et le nombre àn. - Pour chaque paire
i < jtelle queisConnected[i][j] = 1, trouvez les racines deiet dej. - Dans
find, remontez jusqu’à la racine, puis reparcourez le chemin et faites pointer chaque ville qui s’y trouve vers la racine. - Si les racines sont différentes, rattachez la racine de rang inférieur sous l’autre, ajoutez 1 au rang en cas d’égalité, et soustrayez 1 au nombre.
- Renvoyez le nombre.
def findCircleNum(isConnected):
n = len(isConnected)
parent = list(range(n))
rank = [0] * n
def find(city):
root = city
while parent[root] != root:
root = parent[root]
# Path compression: point every city on the way straight at the root.
while parent[city] != root:
up = parent[city]
parent[city] = root
city = up
return root
provinces = n
for i in range(n):
for j in range(i + 1, n): # the matrix is symmetric, so the upper half is enough
if isConnected[i][j] == 1:
a, b = find(i), find(j)
if a == b:
continue
# Union by rank: hang the shorter tree under the taller one.
if rank[a] < rank[b]:
a, b = b, a
parent[b] = a
if rank[a] == rank[b]:
rank[a] += 1
# Two provinces just became one.
provinces -= 1
return provinces
Pièges et cas limites
- Ne tenir compte que des routes directes. Les villes 0 et 2 du deuxième exemple ont un 0 entre elles et appartiennent tout de même à la même province.
- Compter les 1 et diviser par deux. Trois villes qui sont toutes reliées entre elles ont trois routes et une province.
- Dans union-find, décrémenter le compteur pour chaque 1, au lieu de le faire uniquement lorsque les deux racines sont différentes.
- Comparer
parent[i]etparent[j]. Deux villes d’un même groupe peuvent avoir des parents différents si l’une se trouve plus en profondeur ; comparefind(i)etfind(j). - Attacher la ville
jelle-même, comme dansparent[j] = find(i). Sijappartenait déjà à un groupe, le reste de ce groupe est exclu de la fusion.
Questions fréquentes3
Quelle est la complexité temporelle de Number of Provinces ?
O(n²) avec une recherche dans le graphe ou une structure union-find, car les deux parcourent chaque entrée de la matrice n × n une fois. Union-find ajoute un facteur α(n), la fonction inverse d’Ackermann, qui est au plus égal à 4 en pratique. L’espace supplémentaire est de O(n).
Faut-il utiliser DFS, BFS ou union-find pour le nombre de provinces ?
Les trois renvoient le même nombre en temps O(n²). DFS ou BFS est le plus rapide à écrire. Union-find est le meilleur outil lorsque tu dois aussi répondre à de nombreuses questions du type « ces deux villes appartiennent-elles à la même province ? », car chaque réponse prend un temps presque constant.
En quoi le nombre de provinces diffère-t-il du nombre d’îles ?
Les deux comptent les composantes connexes. Dans Nombre d’îles, le graphe est une grille, chaque carré a au plus quatre voisins, et le travail est en O(rows × cols). Ici, le graphe est une matrice d’adjacence : n’importe quelle ville peut être reliée à n’importe quelle autre, et lister les voisins d’une ville revient à lire une ligne entière de n entrées.
Problèmes similaires
Des problèmes qui reposent sur les mêmes idées. En résoudre deux ou trois, c’est ce qui ancre un schéma.
def findCircleNum(isConnected):
# Écrivez le code iciTest #1
Test #2
Argument
isConnected = [[1, 0, 0, 1], [0, 1, 1, 0], [0, 1, 1, 0], [1, 0, 0, 1]]
Résultat attendu
2