LeetCode: número de componentes conectados en un gráfico no dirigido (Java)

Dados n nodos etiquetados de 0 a n – 1 y una lista de bordes no dirigidos (cada borde es un par de nodos), escriba una función para encontrar el número de componentes conectados en un gráfico no dirigido.

Por ejemplo:

     0          3
     |          |
     1 --- 2    4

Dado n = 5 y aristas = [[0, 1], [1, 2], [3, 4]]devuelve 2.

Solución Java – Union-find

Este problema se puede resolver usando union-find maravillosamente. Inicialmente, hay n nodos. Los nodos que están involucrados en cada borde se fusionan.

public int countComponents(int n, int[][] edges) {
    int count = n;
 
    int[] root = new int[n];
    // initialize each node is an island
    for(int i=0; i<n; i++){
        root[i]=i;        
    }
 
    for(int i=0; i<edges.length; i++){
        int x = edges[i][0];
        int y = edges[i][1];
 
        int xRoot = getRoot(root, x);
        int yRoot = getRoot(root, y);
 
        if(xRoot!=yRoot){
            count--;
            root[xRoot]=yRoot;
        }
 
    }
 
    return count;
}
 
public int getRoot(int[] arr, int i){
    while(arr[i]!=i){
        arr[i]= arr[arr[i]];
        i=arr[i];
    }
    return i;
}

Hay k bucles y cada bucle que procesa la matriz raíz cuesta log (n). Por lo tanto, la complejidad del tiempo es O (k * log (n)).