Find the Connected Component in the Undirected Graph

题目：

Find the number connected component in the undirected graph. Each node in the graph contains a label and a list of its neighbors.

分析：

图中的bfs是个hash table + queue的情况，hash table用于记录是否访问过该节点，而queue用于暂存bfs。

具体模板为：

body
1. 开hash table，起步时候所有value都为false
2. for所有的node，如果没visit过，就对他做bfs
bfs
1. 传入的参数为(node, &visited, &res)，注意这里不会传递整张图进来
2. 开queue，把node push进去，把node标为visited，把值放入vector<int> region
3. for 所有node的neighbor，如果没visit过，就push进queue，并标记为visited
4. 把region放入res

接口：

* Definition for Undirected graph.
struct UndirectedGraphNode {
    int label;
    vector<UndirectedGraphNode *> neighbors;
    UndirectedGraphNode(int x) : label(x) {};
};

解法：

class Solution {
public:
    /**
     * @param nodes a array of Undirected graph node
     * @return a connected set of a Undirected graph
     */
    void bfs(UndirectedGraphNode* node, 
                unordered_map<UndirectedGraphNode*, bool> &visited, 
                vector<vector<int> > &res) {
        vector<int> region;
        queue<UndirectedGraphNode*> Q;
        Q.push(node);
        while (!Q.empty() ) {
            UndirectedGraphNode* temp = Q.front();
            Q.pop();
            region.push_back(temp->label);
            visited[temp] = true;
            for (int i = 0; i < temp->neighbors.size(); i++) {
                if (visited[temp->neighbors[i]] == false) {
                    Q.push(temp->neighbors[i]);
                    visited[temp->neighbors[i] ] = true;
                }
            }
        }
        res.push_back(region);
    } 

    vector<vector<int>> connectedSet(vector<UndirectedGraphNode*>& nodes) {
        // Write your code here
        unordered_map<UndirectedGraphNode*, bool> visited;
        for (int i = 0; i < nodes.size(); i++) {
            visited[nodes[i] ] = false;
        }
        vector<vector<int> > res;
        for (int i = 0; i < nodes.size(); i++) {
            if (visited[nodes[i] ] == false) {
                bfs(nodes[i], visited, res);
            }
        }
        return res;
    }
};