My Union Find Solution in Java


  • 0
    L

    The idea is very straightforward: When a union operation is successful, the number of connected components decrease by one.

    public class Solution {
    public int countComponents(int n, int[][] edges) {
        //use this map to find the representative of each component
        Map<Integer, Integer> mymap = new HashMap<Integer, Integer>();
        //make disjoint sets
        for (int i = 0; i < n; i++) {
            mymap.put(i, i);
        }
        int num_components = n;
        //union sets
        for (int i = 0; i < edges.length; i++) {
            int x = edges[i][0];
            int y = edges[i][1];
            if (union(x, y, mymap) == true){
                //a union operation is successfull, one less component
                num_components--;
            }
        }
        return num_components;
    }
    //find the representative
    public int find(int key, Map<Integer, Integer> mymap) {
        int value = mymap.get(key);
        if (value == key) {
            return value;
        }
        return find(value, mymap);
    }
    
    public boolean union(int x, int y, Map<Integer, Integer> mymap) {
        int xRoot = find(x, mymap);
        int yRoot = find(y, mymap);
        if (xRoot == yRoot) {
            return false;
        }
        //union
        mymap.put(yRoot, xRoot);
        return true;
    }
    

    }


Log in to reply
 

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