Number of Components

Number of Connected Components in an Undirected Graph, 维护一个numOfComponents的变量。在完成每一组edge的union以后，return这个numOfComponents。

public class Solution {
    public int countComponents(int n, int[][] edges) {
        if (n <= 1) {
            return n;
        }

        UnionFind uf = new UnionFind(n);
        for (int[] e: edges) {
            int u = e[0];
            int v = e[1];
            uf.union(u, v);
        }

        return uf.getNumOfComponents();
    }
}

class UnionFind {
    private Map<Integer, Integer> parent = new HashMap<Integer, Integer>();
    private Map<Integer, Integer> size = new HashMap<Integer, Integer>();
    private int numOfComponents;

    public UnionFind(int n) {
        for (int i = 0; i < n; i++) {
            parent.put(i, i);
            size.put(i, 1);
        }
        numOfComponents = n;
    }

    public int find(int x) {
        int father = parent.get(x);
        while (father != parent.get(father)) {
            father = parent.get(father);
        }

        while (parent.get(x) != father) {
            int next = parent.get(x);
            parent.put(x, father);
            x = next;
        }

        return father;
    }

    public void union(int x, int y) {
        int x_father = find(x);
        int y_father = find(y);

        if (x_father != y_father) {
            int x_size = size.get(x_father);
            int y_size = size.get(y_father);
            if (x_size > y_size) {
                parent.put(y_father, x_father);
                size.put(x_father, x_size + y_size);
            } else {
                parent.put(x_father, y_father);
                size.put(y_father, x_size + y_size);
            }
            numOfComponents--;
        }
    }

    public int getNumOfComponents() {
        return numOfComponents;
    }
}

Find the Weak Connected Component in the Directed Graph， 把所有的node与neighbors都union了以后，遍历uf的parent map, 得到每一组group。

/**
 * Definition for Directed graph.
 * class DirectedGraphNode {
 *     int label;
 *     ArrayList<DirectedGraphNode> neighbors;
 *     DirectedGraphNode(int x) { label = x; neighbors = new ArrayList<DirectedGraphNode>(); }
 * };
 */
public class Solution {
    /**
     * @param nodes a array of Directed graph node
     * @return a connected set of a directed graph
     */
    public List<List<Integer>> connectedSet2(ArrayList<DirectedGraphNode> nodes) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (nodes == null || nodes.size() == 0) {
            return result;
        }

        Set<DirectedGraphNode> set = new HashSet<DirectedGraphNode>(nodes);
        UnionFind uf = new UnionFind(set);

        for (DirectedGraphNode node: nodes) {
            for (DirectedGraphNode neighbor: node.neighbors) {
                uf.union(node.label, neighbor.label);
            }
        }

        Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
        for (int key: uf.parent.keySet()) {
            int parent = uf.find(key);
            if (!map.containsKey(parent)) {
                map.put(parent, new ArrayList<Integer>());
            }
            map.get(parent).add(key);
        }

        for (List<Integer> list: map.values()) {
            Collections.sort(list);
            result.add(list);
        }
        return result;
    }
}

class UnionFind {
    Map<Integer, Integer> parent = new HashMap<Integer, Integer>();
    Map<Integer, Integer> size = new HashMap<Integer, Integer>();

    public UnionFind(Set<DirectedGraphNode> set) {
        for (DirectedGraphNode node: set) {
            parent.put(node.label, node.label);
            size.put(node.label, 1);
        }
    }

    public int find(int x) {
        int father = parent.get(x);
        while (father != parent.get(father)) {
            father = parent.get(father);
        }

        while (parent.get(x) != father) {
            int next = parent.get(x);
            parent.put(x, father);
            x = next;
        }

        return father;
    }

    public void union(int x, int y) {
        int x_father = find(x);
        int y_father = find(y);

        if (x_father != y_father) {
            int x_size = size.get(x_father);
            int y_size = size.get(y_father);

            if (x_size > y_size) {
                parent.put(y_father, x_father);
                size.put(x_father, x_size + y_size);
            } else {
                parent.put(x_father, y_father);
                size.put(y_father, x_size + y_size);
            }
        }
    }
}