C++ DFS solution


  • 0
    class Solution {
    public:
        int countComponents(int n, vector<pair<int, int>>& edges) {
            vector<vector<int>> graph(n);
            for (auto &edge : edges) {
                graph[edge.first].push_back(edge.second);
                graph[edge.second].push_back(edge.first);
            }
            set<int> visited;
            int cc = 0;
            
            std::function<void(int)> traverse = [&] (int n) {
                if (visited.count(n)) return;
                visited.insert(n);
                for (auto child : graph[n]) {
                    traverse(child);
                }
            };
            
            for (int i = 0; i < n; ++i) {
                if (visited.count(i)) continue;
                ++cc;
                traverse(i);
            }
            return cc;
        }
    };

Log in to reply
 

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