[Leetcode] 0323. Número de componentes conectados en un gráfico no dirigido

Explore diversas soluciones LeetCode en Python, C++, JavaScript, SQL y TypeScript. Ideal para preparación de entrevistas, aprendizaje y práctica de código en múltiples lenguajes de programación. Enlace de repositorio de Github

Tabla de contenido

Medio

Tienes una gráfica de norte nodos.Se te da un número entero. norte y una matriz bordes dónde bordes [i] = [a _i , b _i ] indica que hay un borde entre _AI y b _yo en el gráfico.

Devolver el número de componentes conectados en el gráfico.

Ejemplo 1:

Aporte: n = 5, aristas = [[0,1],[1,2],[3,4]]
Producción: 2

Ejemplo 2:

Aporte: n = 5, aristas = [[0,1],[1,2],[2,3],[3,4]]
Producción: 1

Restricciones:

1 <= norte <= 2000
1 <= bordes.longitud <= 5000
bordes[i].longitud == 2
0 <= a _yo <= b _yo < n
a _i ! = b _i
No hay bordes repetidos.

Pitón

				
					# time complexity: O(V + E * α(n)) is the inverse Ackermann function
# space complexity: O(V)
from typing import List


class UnionFind():
    def __init__(self, n):
        self.parents = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]

    def find(self, node):
        while node != self.parents[node]:
            node = self.parents[node]
        return node

    def uion(self, nodeX, nodeY):
        parentX = self.find(nodeX)
        parentY = self.find(nodeY)

        if parentX == parentY:
            return

        if self.rank[parentX] > self.rank[parentY]:
            self.parents[parentY] = self.parents[parentX]
        elif self.rank[parentX] < self.rank[parentY]:
            self.parents[parentX] = self.parents[parentY]
        else:
            self.parents[parentX] = self.parents[parentY]
            self.rank[parentY] += 1


class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        disjointUnionSet = UnionFind(n)
        for startVertex, endVertex in edges:
            disjointUnionSet.uion(startVertex, endVertex)

        parent = set()
        for i in range(n):
            parent.add(disjointUnionSet.find(i))
        return len(set(parent))


n = 4
edges = [[0, 1], [2, 3], [1, 2]]
print(Solution().countComponents(n, edges))

Medio

Pitón

Artículos relacionados