Number of Provinces

Q: ¿Cuál es la complejidad temporal de Number of Provinces?

O(n²) tanto con una búsqueda en grafos como 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 como máximo es 4 para cualquier entrada real. El espacio adicional es O(n) para las marcas de visitado, o para los arreglos de padres y rangos.

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 cuando se proporciona la matriz completa de una vez. Union-find es la mejor herramienta cuando las carreteras llegan una por una, o cuando también debes responder si dos ciudades comparten una provincia, porque procesa cada carretera y cada pregunta en tiempo casi constante sin realizar una nueva búsqueda.

Q: ¿Qué hacen la compresión de caminos y la unión por rango en union-find?

La unión por rango adjunta el árbol más corto bajo el más alto cuando se fusionan dos grupos, lo que mantiene la altura de cada árbol en, como máximo, log n. La compresión de caminos hace que cada nodo por el que pasa find apunte directamente a la raíz, así que las búsquedas posteriores desde esos nodos requieren un paso. Con ambas técnicas, cualquier secuencia de m operaciones cuesta O(m α(n)), lo que se comporta como tiempo lineal.

Q: ¿En qué se diferencia el número de provincias del número de islas?

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 se presenta como una matriz de adyacencia: cualquier ciudad puede conectarse con cualquier otra, y lees una fila completa de n entradas para enumerar los vecinos de una ciudad.

MedioUnion-find Grafos

+10

Hay n ciudades, numeradas de 0 a n-1. Recibes una matriz n × n isConnected como una lista de filas: isConnected[i][j] es 1 cuando una carretera conecta directamente la ciudad i con la ciudad j, y 0 cuando no lo hace. Las carreteras funcionan en ambos sentidos, por lo que la matriz es simétrica, y se considera que 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 donde 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 que lleva a la ciudad 3, y la ciudad 1 tiene una carretera que lleva a la ciudad 2. No hay ninguna carretera que conecte los dos pares, así que hay 2 provincias.

+15 pruebas ocultas al enviar

Para ir más allá

Cada carretera se abre en un día determinado. ¿Puedes encontrar el primer día en que todas las ciudades pertenezcan 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 es la matriz de adyacencia de un grafo no dirigido: las ciudades son nodos y un 1 en la fila i, columna j es una arista. Una provincia es un componente conexo, así que la respuesta es el número de componentes. La trampa es que se puede llegar a través de una tercera ciudad: un 0 entre dos ciudades no las sitúa en provincias distintas. Una búsqueda desde cada ciudad no visitada, o una estructura union-find que une los dos extremos de cada arista, cuenta los componentes en O(n²), el tamaño de la propia matriz.

Búsqueda en profundidad desde cada ciudad no visitada

Intuición

Recorre las ciudades en orden. Cuando encuentres una ciudad que ninguna búsqueda anterior haya marcado, no puede pertenecer a una provincia que ya hayas contado, porque cada búsqueda marca toda su provincia. Así que suma uno al recuento y luego marca todas las ciudades a las que esta puede llegar.

Para encontrarlas, usa una pila. Saca una ciudad de la pila, lee su fila de la matriz y añade a la pila todas las ciudades que tengan un 1 en esa fila y aún no estén marcadas, marcándolas al añadirlas. En el segundo ejemplo, la búsqueda desde la ciudad 0 añade la ciudad 1 a la pila, y la fila de la ciudad 1 añade después la ciudad 2, aunque la fila 0 tenga un 0 para la ciudad 2. Seguir las filas de esta manera es lo que permite encontrar las ciudades conectadas solo a través de otras.

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

Una búsqueda recursiva se lee mejor, pero en una provincia con forma de línea larga, las llamadas se anidan una vez por ciudad. Con n = 150, eso es seguro; el mismo código en un grafo con 10^5 nodos desborda la pila de llamadas, así que vale la pena acostumbrarse a usar una pila explícita.

Algoritmo

Crea una marca de visitado para cada ciudad y establece el contador en 0.
Recorre las ciudades en orden y omite cualquier ciudad que ya se haya visitado.
Para una ciudad no visitada, suma 1 al contador, márcala y añádela a una pila.
Mientras haya ciudades en la pila, extrae una y añade todas las ciudades de su fila que tengan un 1 y aún no se hayan visitado; márcalas 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

Invierte la pregunta. Empieza con n provincias, una por ciudad. Cada 1 de la matriz indica que dos ciudades pertenecen al mismo grupo: si aún están en grupos diferentes, une los grupos y la cantidad disminuye en uno. Después del último camino, la cantidad es la respuesta. Solo necesitas las entradas por encima de la diagonal, porque la matriz es simétrica y la diagonal conecta una ciudad consigo misma. En el segundo ejemplo, la cantidad empieza en 5. El 1 en (0, 1) une las ciudades 0 y 1 (quedan 4), y el 1 en (1, 2) encuentra que la ciudad 1 pertenece al grupo de la ciudad 0 e incorpora la ciudad 2 (quedan 3). Las ciudades 3 y 4 no tienen ningún 1 por encima de la diagonal, así que la respuesta es 3.

Una estructura union-find, también llamada unión de conjuntos disjuntos, almacena cada grupo como un árbol. parent[c] apunta un nivel hacia arriba, y la ciudad en la cima, cuyo padre es ella misma, es la raíz del grupo. Dos ciudades están en el mismo grupo exactamente cuando find las recorre hasta llegar a la misma raíz. Para unir dos grupos, apunta una raíz a la otra.

Dos reglas mantienen los árboles equilibrados. La unión por rango cuelga el árbol más bajo bajo el más alto, de modo que un árbol de altura h contiene al menos 2^h ciudades y ningún recorrido supera log n. La compresión de caminos va más allá: una vez que find ha encontrado la raíz, apunta directamente a ella todas las ciudades por las que pasó, así que la siguiente búsqueda desde cualquiera de ellas requiere un solo paso. Sin ninguna de estas reglas, unir las ciudades de una cadena larga en un orden desfavorable crea un árbol que es un único camino, y cada find recorre O(n) pasos.

Con ambas reglas, cada find cuesta O(α(n)) amortizado, donde α es la función inversa de Ackermann, que se mantiene como máximo en 4 para cualquier n que pueda almacenar una computadora. Leer la matriz sigue costando O(n²), así que ese es el costo total, y los arreglos parent y rank ocupan O(n) espacio. La estructura resulta útil cuando los caminos llegan uno a uno: mantiene la cantidad actualizada después de cada nuevo camino sin tener que buscar de nuevo.

Algoritmo

Establece parent[c] = c y rank[c] = 0 para cada ciudad, y establece el contador en n.
Para cada par i < j con isConnected[i][j] = 1, encuentra las raíces de i y j.
En find, recorre el camino hasta la raíz y luego vuelve a recorrer el mismo camino, apuntando directamente a la raíz cada ciudad que lo forma.
Si las raíces son diferentes, une la raíz de menor rango bajo la otra, suma 1 al rango en caso de empate y resta 1 al contador.
Devuelve el contador.

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

La mayoría de las respuestas incorrectas interpretan un 0 como prueba de que dos ciudades están separadas o cuentan algo que no son componentes.

Comprobar solo las carreteras directas. Las ciudades 0 y 2 del segundo ejemplo tienen un 0 entre ellas y aun así comparten una provincia a través de la ciudad 1. Cualquier recuento basado únicamente en las carreteras directas no lo detecta; por ejemplo, contar las filas distintas da 5 en lugar de 3.
Contar los 1 y dividir entre dos. Eso cuenta carreteras, no provincias: tres ciudades que están todas conectadas entre sí tienen tres carreteras y una provincia.
En union-find, reducir el recuento con cada 1 en vez de hacerlo solo cuando las dos raíces son distintas. Una carretera dentro de un grupo que ya está unido no debe cambiar el recuento.
Comparar los padres en vez de las raíces. parent[i] == parent[j] puede ser falso para dos ciudades del mismo grupo cuando una está más abajo en el árbol; compara siempre find(i) con find(j).
Unir la ciudad j en vez de su raíz, como en parent[j] = find(i). Si j ya estaba en un grupo, el resto de ese grupo queda excluido de la unión.
Usar recursión en grafos grandes. Una búsqueda recursiva, o un find recursivo sin unión por rango, avanza un nivel por ciudad en un grafo con forma de cadena. Eso está bien con 150 ciudades, pero provoca un desbordamiento de pila con 10^5.

Preguntas frecuentes4

¿Cuál es la complejidad temporal de Number of Provinces?

O(n²) tanto con una búsqueda en grafos como 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 como máximo es 4 para cualquier entrada real. El espacio adicional es O(n) para las marcas de visitado, o para los arreglos de padres y rangos.

¿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 cuando se proporciona la matriz completa de una vez. Union-find es la mejor herramienta cuando las carreteras llegan una por una, o cuando también debes responder si dos ciudades comparten una provincia, porque procesa cada carretera y cada pregunta en tiempo casi constante sin realizar una nueva búsqueda.

¿Qué hacen la compresión de caminos y la unión por rango en union-find?

La unión por rango adjunta el árbol más corto bajo el más alto cuando se fusionan dos grupos, lo que mantiene la altura de cada árbol en, como máximo, log n. La compresión de caminos hace que cada nodo por el que pasa find apunte directamente a la raíz, así que las búsquedas posteriores desde esos nodos requieren un paso. Con ambas técnicas, cualquier secuencia de m operaciones cuesta O(m α(n)), lo que se comporta como tiempo lineal.

¿En qué se diferencia el número de provincias del número de islas?

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 se presenta como una matriz de adyacencia: cualquier ciudad puede conectarse con cualquier otra, y lees una fila completa de n entradas para enumerar los vecinos de una ciudad.

Python

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

Casos de prueba

Caso 1

Caso 2

Entrada

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

Esperado