Simple Java Code - No fancy Data Structure


  • 0

    Similar problem as Number of Islands I & II.

    public class Solution {
        public int countComponents(int n, int[][] edges) {
            if (edges.length == 0) return n; 
            int[] roots = new int[n]; 
            
            for (int i = 0; i < n; i++) roots[i] = i; 
            for (int i = 0; i < edges.length; i++)
                updateRoot(edges[i][0], edges[i][1], roots); 
            
            int cnt = 0; 
            for (int i = 0; i < n; i++) 
                if (roots[i] == i) cnt++; 
            return cnt; 
        }
    
        public void updateRoot(int node1, int node2, int[] roots) {
            while (roots[node1] != node1) node1 = roots[node1];
            while (roots[node2] != node2) node2 = roots[node2]; 
            if (node1 != node2) roots[node1] = node2; 
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.