Number of Connected Components i

基本的graph搜索题

1： DFS

class Solution {
public:
    int countComponents(int n, vector<pair<int, int>>& edges) {
        if(edges.empty()) return n;
        vector<vector<int>> graph(n, vector<int>());
        int cnt = 0;
        for(auto it : edges){
            graph[it.first].push_back(it.second);
            graph[it.second].push_back(it.first);
        }
        vector<bool> visited(n, false);
        for(int i=0; i<n; i++){
            if(!visited[i]){
                dfs(graph, visited, i);
                cnt++;
            }
        }
        return cnt;
    }
    
    void dfs(vector<vector<int>> &graph, vector<bool> &visited, int cur){
        if(visited[cur]) return;
        visited[cur] = true;
        for(int it : graph[cur]){
            if(!visited[it]){
                dfs(graph, visited, it);
            }
        }
    }
};

2. BFS:

class Solution {
public:
    int countComponents(int n, vector<pair<int, int>>& edges) {
        if(edges.empty()) return n;
        vector<vector<int>> graph(n, vector<int>());
        int cnt = 0;
        for(auto it : edges){
            graph[it.first].push_back(it.second);
            graph[it.second].push_back(it.first);
        }
        vector<bool> visited(n, false);
        queue<int> q;
        for(int i=0; i<n; i++){
            if(!visited[i]){
                cnt++;
                q.push(i);
            }
            while(!q.empty()){
                int cur = q.front(); q.pop();
                visited[cur] = true;
                for(int it : graph[cur]){
                    if(!visited[it]){
                        visited[it] = true;
                        q.push(it);
                    }
                }
            }
        }
        return cnt;      
    }
};

3. 并查集，并查集直观找num of edges， 所以用n - num of edges就是结果

class Solution {
    
    unordered_map<int, int> mp;
    int find_(int i){
        int parent = mp[i];
        while(parent != mp[parent]){
            parent = mp[parent];
        }
        int next;
        while(i != mp[i]){
            next = mp[i];
            mp[i] = parent;
            i = next;
        }
        return parent;
    }
    
    void union_(int p, int q){
        int parent_p = find_(p);
        int parent_q = find_(q);
        if(parent_p != parent_q){
            mp[parent_p] = parent_q;
        }
    }
    
public:
    int countComponents(int n, vector<pair<int, int>>& edges) {
        int cnt = 0;
        
        for(int i=0; i<n; i++){
            mp[i] = i;
        }
        
        for(auto it : edges){
            if(find_(it.first) != find_(it.second)){
                union_(it.first, it.second);
                cnt++;
            }
        }
        return n-cnt;
    }
};