Find the number connected component in the undirected graph. Each node in the graph contains a label and a list of its neighbors. (a connected component (or just component) of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph.)

Notice

Each connected component should sort by label.

Have you met this question in a real interview?

Yes

Clarification

Learn more about representation of graphs

Example

Given graph:

A------B  C
 \     |  | 
  \    |  |
   \   |  |
    \  |  |
      D   E

Return{A,B,D}, {C,E}. Since there are two connected component which is{A,B,D}, {C,E}

1.可以用bfs, dfs，和 union find (hashmap实现）

/**
 * Definition for Undirected graph.
 * class UndirectedGraphNode {
 *     int label;
 *     ArrayList<UndirectedGraphNode> neighbors;
 *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
 * };
 */

class UnionFind {
    HashMap<Integer, Integer> father = null;
    public UnionFind(HashSet<Integer> set) {
        father = new HashMap<Integer, Integer>();
        for (Integer cur : set) {
            father.put(cur, cur);
        }
    }

    public int find(int a) {
        int parent = father.get(a);

        while (parent != father.get(parent)) {
            parent = father.get(parent);
        }

        int temp = -1;
        int fa = father.get(a);

        while (fa != parent) {
            temp = father.get(fa);
            father.put(fa, parent);
            fa = temp;
        }

        return parent;
    }

    public void connect(int a, int b) {
        int root_a = find(a);
        int root_b = find(b);

        if (root_a != root_b) {
            father.put(root_a, root_b);
        }
    }
}


public class Solution {
    /*
     * @param nodes: a array of Undirected graph node
     * @return: a connected set of a Undirected graph
     */
    public List<List<Integer>> connectedSet(List<UndirectedGraphNode> nodes) {
        // write your code here
        List<List<Integer>> ans = new ArrayList<>();
        HashSet<Integer> set = new HashSet<Integer>();
        for (UndirectedGraphNode node : nodes) {
            set.add(node.label);
            for (UndirectedGraphNode neighbor : node.neighbors) {
                set.add(neighbor.label);
            }
        }
        UnionFind uf = new UnionFind(set);
        for (UndirectedGraphNode node : nodes) {
            for (UndirectedGraphNode neighbor : node.neighbors) {
                uf.connect(node.label, neighbor.label);
            }
        }

        HashMap<Integer, HashSet<Integer>> map = new HashMap<Integer, HashSet<Integer>>();
        for (Integer cur : set) {
            if (cur == uf.find(cur)) {
                map.put(cur, new HashSet<Integer>());
            }
        }

        for (Integer cur : set) {
            map.get(uf.find(cur)).add(cur);
        }

        for (HashSet<Integer> value : map.values()) {
            List<Integer> current = new ArrayList<>();
            for (Integer cur : value) {
                current.add(cur);
            }
            Collections.sort(current);
            ans.add(current);
        }
        return ans;



    }
}