Clean C++ BFS solution


  • 0
    S
    class Solution {
    public:
        int countComponents(int n, vector<pair<int, int>>& edges) {
            int ret = 0;
            vector<bool> visited(n, false);
            unordered_map<int, vector<int>> graph = make_graph(edges);
            for ( int i = 0; i < n; i++ ) {
                if (!visited[i]) {
                    bfs(i, graph, visited);
                    ret++;
                }
            }
            return ret;
        }
    private:
        unordered_map<int, vector<int>> make_graph(vector<pair<int, int>>& edges) {
            unordered_map<int, vector<int>> ret;
            for ( int i = 0; i < edges.size(); i++ ) {
                int key = edges[i].first;
                int neigh = edges[i].second;
                ret[key].push_back(neigh);
                ret[neigh].push_back(key);
            }
            return ret;
        }
        
        void bfs(int node, unordered_map<int, vector<int>>& graph, vector<bool>& visited) {
            visited[node] = true;
            queue<int> Q;
            Q.push(node);
            while(!Q.empty()) {
                int key = Q.front();
                Q.pop();
                for ( int i = 0; i < graph[key].size(); i++ ) {
                    int cur = graph[key][i];
                    if (!visited[cur]) {
                        visited[cur] = true;
                        Q.push(cur);
                    }
                }
            }
        }
    };
    

    Explanation:
    Store edges into a hash table for easy finding. Becasue it is an undirected graph, therefore, storing a edge in both node lists. For example, (1,0). In the hash table, key: 1 has element 0; and key: 0 has element 1.
    And rest of code follows the basic bfs structure.

    One bfs() can find all connected nodes. And the times of bfs() called is the final answers.


Log in to reply
 

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