Number of Connected Components in an Undirected Graph (Leetcode)

题目：

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph.

分析：

这道题目leetcode和lintcode上面接口不一样，所以从新做了一遍。重点和valid graph tree那个题目一样，是把点-边的集合变成一个邻接表。bfs和dfs解法写在一起了。

解法bfs + dfs：

class Solution {
public:
    void bfs(int i, vector<vector<int> > &neighbors, vector<bool> &visited) {
        queue<int> Q;
        Q.push(i);
        while (!Q.empty() ) {
            int temp = Q.front();
            Q.pop();
            for (int j = 0; j < neighbors[temp].size(); j++) {
                if (visited[neighbors[temp][j] ] == true) {
                    continue;
                }
                Q.push(neighbors[temp][j]);
                visited[neighbors[temp][j] ] = true;
            }
        }
    }

    void dfs(int i, vector<vector<int> > &neighbors, vector<bool> &visited) {
        if (visited[i] == true) {
            return;
        }
        visited[i] = true;
        for (int j = 0; j < neighbors[i].size(); j++) {
            if (visited[neighbors[i][j] ] == true) {
                continue;
            }
            dfs(neighbors[i][j], neighbors, visited);
        }
    }

    int countComponents(int n, vector<pair<int, int>>& edges) {
        vector<vector<int> > neighbors(n, vector<int>() );
        for (int i = 0; i < edges.size(); i++) {
            int first = edges[i].first;
            int second = edges[i].second;
            neighbors[first].push_back(second);
            neighbors[second].push_back(first);
        }
        vector<bool> visited(n, false);
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (visited[i] == false) {
                count++;
                dfs(i, neighbors, visited);
                //bfs(i, neighbors, visited);
            }
        }
        return count;
    }
};