Number of Provinces

Q: ¿Cuál es la complejidad temporal del número de provincias?

O(n²) con una búsqueda en grafos o con union-find, porque ambos leen cada entrada de la matriz n × n una vez. Union-find añade un factor α(n), la función inversa de Ackermann, que en la práctica es como máximo 4. El espacio adicional es O(n).

Q: ¿Deberías usar DFS, BFS o union-find para el problema «Número de provincias»?

Los tres devuelven el mismo recuento en tiempo O(n²). DFS o BFS son los más breves de escribir. Union-find es la mejor herramienta cuando también tienes que responder muchas preguntas de la forma «¿estas dos ciudades comparten una provincia?», porque cada respuesta lleva un tiempo casi constante.

Q: ¿En qué se diferencia Number of Provinces de Number of Islands?

Ambos cuentan los componentes conectados. En Number of Islands, el grafo es una cuadrícula, cada casilla tiene como máximo cuatro vecinos y el trabajo es O(rows × cols). Aquí el grafo es una matriz de adyacencia: cualquier ciudad puede conectarse con cualquier otra, y enumerar los vecinos de una ciudad requiere leer una fila completa de n entradas.

MedioUnion-find Grafos

+10

Hay n ciudades, numeradas del 0 al n-1. isConnected[i][j] es 1 cuando una carretera conecta directamente la ciudad i con la ciudad j, y 0 en caso contrario. Las carreteras funcionan en ambos sentidos, por lo que la matriz es simétrica, y cada ciudad está conectada consigo misma.

Una provincia es un grupo de ciudades que pueden llegar todas unas a otras, directamente o a través de otras ciudades, sin que ninguna carretera salga del grupo. Devuelve el número de provincias.

Función

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

isConnectedinteger-2d-array: la matriz n × n, 1 cuando una carretera conecta directamente dos ciudades
Devuelveinteger: el número de provincias

Restricciones

1 ≤ n ≤ 150, donde n = isConnected.length
isConnected[i].length = n
isConnected[i][j] es 0 o 1
isConnected[i][i] = 1
isConnected[i][j] = isConnected[j][i]

Ejemplos

Entrada: isConnected = [[1, 0, 0, 1], [0, 1, 1, 0], [0, 1, 1, 0], [1, 0, 0, 1]]
Salida: 2
Explicación: La ciudad 0 tiene una carretera hacia la ciudad 3, y la ciudad 1 tiene una carretera hacia la ciudad 2. Ninguna carretera conecta los dos pares, así que hay 2 provincias.

Para ir más allá

Cada carretera se abre ahora en un día determinado. ¿Puedes encontrar el primer día en que todas las ciudades pertenecen a una sola provincia?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

La matriz describe un grafo no dirigido: las ciudades son nodos y cada 1 es una arista. Una provincia es un componente conexo, y un 0 entre dos ciudades no las separa cuando una tercera ciudad conecta a ambas. Una búsqueda desde cada ciudad no visitada, o una estructura union-find sobre cada arista, cuenta los componentes en O(n²).

Búsqueda en profundidad desde cada ciudad no visitada

Intuición

Una ciudad sin marcar no puede pertenecer a una provincia que ya hayas contado, porque cada búsqueda marca toda su provincia. Así que inicia una nueva. La búsqueda sigue las filas de la matriz: en el segundo ejemplo, la búsqueda desde la ciudad 0 llega a la ciudad 1, y la fila de la ciudad 1 llega después a la ciudad 2, aunque la fila 0 tiene un 0 para la ciudad 2.

Cada ciudad se extrae una vez y se lee su fila de n entradas, así que lees la matriz una vez: O(n²) de tiempo. Las marcas y la pila contienen como máximo n ciudades, así que el espacio adicional es O(n).

Algoritmo

Crea una marca de visitado para cada ciudad y establece el contador en 0.
Recorre las ciudades en orden y omite las que ya se hayan visitado.
En una ciudad no visitada, suma 1 al contador, márcala y ponla en una pila.
Mientras haya ciudades en la pila, saca una y añade a la pila todas las ciudades de su fila que tengan un 1 y aún no se hayan visitado, marcándolas al añadirlas.
Devuelve el contador.

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 con compresión de caminos y unión por rango

Intuición

Empieza con n provincias, una por ciudad. Cada 1 por encima de la diagonal indica que dos ciudades pertenecen al mismo grupo: si sus grupos son distintos, únelos y reduce el recuento en uno. En el segundo ejemplo, el recuento empieza en 5, (0, 1) une las ciudades 0 y 1, (1, 2) incorpora la ciudad 2 a su grupo, y quedan 3 provincias.

Union-find almacena cada grupo como un árbol: parent[c] apunta un nivel hacia arriba, y dos ciudades comparten un grupo cuando find recorre ambas hasta llegar a la misma raíz. Si no se hace nada, las uniones pueden formar un único camino largo que cada find recorre en O(n) pasos. La unión por rango cuelga el árbol más corto debajo del más alto, de modo que ningún camino supera log n. La compresión de caminos hace que cada ciudad por la que pasa find apunte directamente a la raíz. Juntas, estas técnicas hacen que cada find tenga un coste amortizado de O(α(n)), y α(n) es como máximo 4 en la práctica.

Algoritmo

Establece parent[c] = c y rank[c] = 0 para cada ciudad, y fija el recuento en n.
Para cada par i < j con isConnected[i][j] = 1, encuentra las raíces de i y j.
En find, sube hasta la raíz; después, recorre de nuevo el camino y apunta cada ciudad de ese camino a la raíz.
Si las raíces son distintas, une la raíz de menor rango bajo la otra, suma 1 al rango si hay empate y resta 1 al recuento.
Devuelve el recuento.

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

Errores comunes y casos límite

Confiar únicamente en las carreteras directas. Las ciudades 0 y 2 del segundo ejemplo tienen un 0 entre ellas y aun así pertenecen a la misma provincia.
Contar los 1 y dividir entre dos. Tres ciudades que están todas conectadas entre sí tienen tres carreteras y una provincia.
En union-find, reducir el contador con cada 1 en lugar de hacerlo solo cuando las dos raíces son distintas.
Comparar parent[i] con parent[j]. Dos ciudades del mismo grupo pueden tener padres distintos si una está a mayor profundidad; compara find(i) con find(j).
Vincular la ciudad j directamente, como en parent[j] = find(i). Si j ya pertenecía a un grupo, el resto de ese grupo queda fuera de la unión.

Preguntas frecuentes3

¿Cuál es la complejidad temporal del número de provincias?

O(n²) con una búsqueda en grafos o con union-find, porque ambos leen cada entrada de la matriz n × n una vez. Union-find añade un factor α(n), la función inversa de Ackermann, que en la práctica es como máximo 4. El espacio adicional es O(n).

¿Deberías usar DFS, BFS o union-find para el problema «Número de provincias»?

Los tres devuelven el mismo recuento en tiempo O(n²). DFS o BFS son los más breves de escribir. Union-find es la mejor herramienta cuando también tienes que responder muchas preguntas de la forma «¿estas dos ciudades comparten una provincia?», porque cada respuesta lleva un tiempo casi constante.

¿En qué se diferencia Number of Provinces de Number of Islands?

Ambos cuentan los componentes conectados. En Number of Islands, el grafo es una cuadrícula, cada casilla tiene como máximo cuatro vecinos y el trabajo es O(rows × cols). Aquí el grafo es una matriz de adyacencia: cualquier ciudad puede conectarse con cualquier otra, y enumerar los vecinos de una ciudad requiere leer una fila completa de n entradas.

def findCircleNum(isConnected):
    # Escribe el código aquí

Prueba #1

Prueba #2

Argumento

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

Salida Esperada