Number of Provinces

Q: 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 lisent une fois chaque entrée de la matrice n × n . La structure union-find ajoute un facteur α(n), la fonction d’Ackermann inverse, qui est au plus égale à 4 pour toute valeur d’entrée réelle. L’espace supplémentaire est de O(n) pour les indicateurs de visite, ou pour les tableaux de parents et de rangs.

Q: Faut-il utiliser DFS, BFS ou union-find pour résoudre le problème du nombre de provinces ?

Les trois renvoient le même nombre en O(n²). DFS ou BFS est la méthode la plus courte à écrire lorsque toute la matrice est fournie d’un seul coup. Union-find est le meilleur outil lorsque les routes arrivent une par une, ou lorsque tu dois aussi répondre à la question de savoir si deux villes appartiennent à la même province, car il traite chaque route et chaque question en un temps quasi constant sans nouvelle recherche.

Q: Que font la compression de chemin et l’union par rang dans la structure union-find ?

L’union par rang attache l’arbre le plus court sous le plus grand lorsque deux groupes fusionnent, ce qui maintient la hauteur de chaque arbre à au plus log n. La compression de chemin fait pointer directement vers la racine chaque nœud que find traverse, de sorte que les recherches ultérieures à partir de ces nœuds ne prennent qu’une étape. Avec les deux optimisations, toute séquence de m opérations coûte O(m α(n)), ce qui se comporte comme un temps linéaire.

Q: En quoi le nombre de provinces diffère-t-il du nombre d’îles ?

Les deux comptent les composantes connexes. Dans Number of Islands, le graphe est une grille, chaque case a au plus quatre voisins, et le travail est en O(rows × cols). Ici, le graphe est fourni sous forme de matrice d’adjacence : n’importe quelle ville peut être reliée à n’importe quelle autre, et tu lis une ligne complète de n entrées pour dresser la liste des voisins d’une ville.

MoyenUnion-find Graphes

+10

Il y a n villes, numérotées de 0 à n-1. On vous donne une matrice n × n isConnected sous forme d’une liste de lignes : isConnected[i][j] vaut 1 lorsqu’une route relie directement la ville i à la ville j, et 0 dans le cas contraire. Les routes sont à double sens, donc la matrice est symétrique, et chaque ville est considérée comme 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 en dehors du groupe. Renvoyez le nombre de provinces.

Fonction

findCircleNum(isConnected: integer-2d-array) → integer

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.length
isConnected[i].length = n
isConnected[i][j] vaut 0 ou 1
isConnected[i][i] = 1
isConnected[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, donc il y a 2 provinces.

+15 tests cachés à la soumission

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 seule province ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

La matrice est la matrice d’adjacence d’un graphe non orienté : les villes sont des nœuds et un 1 à la ligne i, colonne j, correspond à une arête. Une province est une composante connexe, donc la réponse est le nombre de composantes. Le piège est qu’on peut passer par une troisième ville : un 0 entre deux villes ne signifie pas qu’elles appartiennent à des provinces différentes. Une recherche à partir de chaque ville non visitée, ou une structure union-find qui fusionne les deux extrémités de chaque arête, compte les composantes en O(n²), soit la taille de la matrice elle-même.

Recherche en profondeur à partir de chaque ville non visitée

Intuition

Parcourez les villes dans l’ordre. Lorsqu’une ville n’a été marquée par aucune recherche précédente, elle ne peut pas appartenir à une province que vous avez déjà comptée, puisque chaque recherche marque toute sa province. Ajoutez donc un au compteur, puis marquez toutes les villes que celle-ci peut atteindre.

Pour les trouver, utilisez une pile. Retirez une ville de la pile, lisez sa ligne de la matrice et empilez toutes les villes dont la valeur dans cette ligne est 1 et qui ne sont pas encore marquées, en les marquant au moment de les empiler. Dans le deuxième exemple, la recherche à partir de la ville 0 empile la ville 1, puis la ligne de la ville 1 ajoute la ville 2, même si la ligne 0 contient un 0 pour la ville 2. C’est en parcourant les lignes de cette manière que l’on trouve les villes reliées uniquement par l’intermédiaire d’autres villes.

Chaque ville est retirée de la pile une seule fois, et son retrait entraîne la lecture de sa ligne, qui contient n entrées : le temps d’exécution total est donc O(n²), car vous lisez la matrice une seule fois. Les marques et la pile contiennent au plus n villes ; l’espace supplémentaire est donc O(n).

Une recherche récursive est plus lisible, mais dans une province formée d’une longue ligne, les appels s’imbriquent une fois par ville. Avec n = 150, cela ne pose pas de problème ; le même code sur un graphe de 10^5 nœuds provoque un dépassement de capacité de la pile d’appels. C’est pourquoi il vaut mieux prendre l’habitude d’utiliser une pile explicite.

Algorithme

Crée un indicateur « vu » pour chaque ville et initialise le compteur à 0.
Parcours les villes dans l’ordre et ignore celles qui ont déjà été vues.
Pour une ville non encore vue, ajoute 1 au compteur, marque-la comme vue et empile-la.
Tant qu’il y a des villes dans la pile, dépile-en une et empile toutes les villes de sa ligne qui ont un 1 et n’ont pas encore été vues, en les marquant au fur et à mesure.
Retourne 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 provinces

Union-find avec compression de chemin et union par rang

Intuition

Reformule la question. Commence avec n provinces, une par ville. Chaque 1 de la matrice indique que deux villes sont reliées : si elles sont encore dans des groupes différents, fusionne les groupes, et le compte diminue de un. Après la dernière route, le compte est la réponse. Tu n’as besoin que des entrées au-dessus de la diagonale, car la matrice est symétrique et la diagonale relie une ville à elle-même. Dans le deuxième exemple, le compte commence à 5. Le 1 en (0, 1) fusionne les villes 0 et 1 (il en reste 4), puis le 1 en (1, 2) constate que la ville 1 appartient au groupe de la ville 0 et y ajoute la ville 2 (il en reste 3). Les villes 3 et 4 n’ont aucun 1 au-dessus de la diagonale, donc la réponse est 3.

Une structure union-find, également appelée union d’ensembles disjoints, stocke chaque groupe sous la forme d’un arbre. parent[c] pointe d’un niveau vers le haut, et la ville tout en haut, dont le parent est elle-même, est la racine du groupe. Deux villes appartiennent au même groupe exactement lorsque find les mène toutes les deux à la même racine. Pour fusionner deux groupes, fais pointer une racine vers l’autre.

Deux règles permettent de garder les arbres plats. L’union par rang rattache l’arbre le plus court sous le plus haut, de sorte qu’un arbre de hauteur h contient au moins 2^h villes et qu’aucun chemin ne dépasse log n. La compression de chemin va plus loin : une fois que find a trouvé la racine, elle fait pointer directement vers cette racine chaque ville traversée, de sorte que la recherche suivante depuis n’importe laquelle d’entre elles ne prend qu’une étape. Sans l’une ou l’autre de ces règles, fusionner les villes d’une longue chaîne dans un ordre défavorable construit un arbre qui n’est qu’un seul chemin, et chaque find parcourt O(n) étapes.

Avec ces deux règles, chaque find coûte O(α(n)) en coût amorti, où α est la fonction inverse d’Ackermann, qui reste inférieure ou égale à 4 pour toute valeur de n qu’un ordinateur peut stocker. La lecture de la matrice coûte toujours O(n²), ce qui donne le coût total, et les tableaux parent et rang occupent O(n) espace. Cette structure est utile lorsque les routes arrivent une par une : elle maintient le compte à jour après chaque nouvelle route sans effectuer de nouvelle recherche.

Algorithme

Définissez parent[c] = c et rank[c] = 0 pour chaque ville, et initialisez le nombre à n.
Pour chaque paire i < j telle que isConnected[i][j] = 1, trouvez les racines de i et de j.
Dans find, remontez jusqu’à la racine, puis parcourez à nouveau le même chemin et reliez directement à la racine chaque ville qui s’y trouve.
Si les racines sont différentes, rattachez la racine de rang inférieur à l’autre, augmentez le rang de 1 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

La plupart des mauvaises réponses considèrent qu’un 0 prouve que deux villes sont séparées, ou comptent autre chose que les composantes.

Vérifier uniquement les routes directes. Les villes 0 et 2 du deuxième exemple ont un 0 entre elles et appartiennent pourtant à la même province via la ville 1. Tout décompte fondé uniquement sur les routes directes passe à côté de cela ; compter les lignes distinctes, par exemple, donne 5 au lieu de 3.
Compter les 1 et diviser par deux. Cela compte les routes, pas les provinces : trois villes qui sont toutes reliées entre elles ont trois routes et une province.
Dans union-find, diminuer le décompte pour chaque 1 au lieu de le faire uniquement lorsque les deux racines sont différentes. Une route à l’intérieur d’un groupe déjà fusionné ne doit pas modifier le décompte.
Comparer les parents au lieu des racines. parent[i] == parent[j] peut être faux pour deux villes du même groupe lorsque l’une se trouve plus profondément dans l’arbre ; compare toujours find(i) et find(j).
Attacher la ville j elle-même au lieu de sa racine, comme dans parent[j] = find(i). Si j appartenait déjà à un groupe, le reste de ce groupe est exclu de la fusion.
La récursion sur de grands graphes. Une recherche récursive, ou un find récursif sans union par rang, parcourt un niveau par ville dans un graphe en forme de chaîne. Cela convient pour 150 villes, mais provoque un débordement de pile avec 10^5.

Questions fréquentes4

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 lisent une fois chaque entrée de la matrice n × n. La structure union-find ajoute un facteur α(n), la fonction d’Ackermann inverse, qui est au plus égale à 4 pour toute valeur d’entrée réelle. L’espace supplémentaire est de O(n) pour les indicateurs de visite, ou pour les tableaux de parents et de rangs.

Faut-il utiliser DFS, BFS ou union-find pour résoudre le problème du nombre de provinces ?

Les trois renvoient le même nombre en O(n²). DFS ou BFS est la méthode la plus courte à écrire lorsque toute la matrice est fournie d’un seul coup. Union-find est le meilleur outil lorsque les routes arrivent une par une, ou lorsque tu dois aussi répondre à la question de savoir si deux villes appartiennent à la même province, car il traite chaque route et chaque question en un temps quasi constant sans nouvelle recherche.

Que font la compression de chemin et l’union par rang dans la structure union-find ?

L’union par rang attache l’arbre le plus court sous le plus grand lorsque deux groupes fusionnent, ce qui maintient la hauteur de chaque arbre à au plus log n. La compression de chemin fait pointer directement vers la racine chaque nœud que find traverse, de sorte que les recherches ultérieures à partir de ces nœuds ne prennent qu’une étape. Avec les deux optimisations, toute séquence de m opérations coûte O(m α(n)), ce qui se comporte comme un temps linéaire.

En quoi le nombre de provinces diffère-t-il du nombre d’îles ?

Les deux comptent les composantes connexes. Dans Number of Islands, le graphe est une grille, chaque case a au plus quatre voisins, et le travail est en O(rows × cols). Ici, le graphe est fourni sous forme de matrice d’adjacence : n’importe quelle ville peut être reliée à n’importe quelle autre, et tu lis une ligne complète de n entrées pour dresser la liste des voisins d’une ville.

Python

def findCircleNum(isConnected):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Entrée

isConnected = [[1, 0, 0, 1], [0, 1, 1, 0], [0, 1, 1, 0], [1, 0, 0, 1]]

Attendu