323. Number of Connected Components in an Undirected Graph

A dynamical connectivity problem. This is a typical application of union find.

1:  class Solution {  
2:  public:  
3:    int countComponents(int n, vector<pair<int, int>>& edges) {  
4:      vector<int> ufs(n, 0);  
5:      for (int i = 0; i < n; i++) ufs[i] = i;  
6:      for (int i = 0; i < edges.size(); i++) {  
7:        int u = edges[i].first;  
8:        int v = edges[i].second;  
9:        while (u != ufs[u]) { ufs[u] = ufs[ufs[u]]; u = ufs[u]; }  
10:        while (v != ufs[v]) { ufs[v] = ufs[ufs[v]]; v = ufs[v]; }  
11:        if (u != v) {  
12:          ufs[u] = ufs[v];  
13:          n--;  
14:        }  
15:      }  
16:      return n;  
17:    }  
18:  };  

Of course, DFS can be used to solve this problem too.

1:  class Solution {  
2:  public:  
3:    int countComponents(int n, vector<pair<int, int>>& edges) {  
4:      vector<vector<int>> graph(n);  
5:      for (int i = 0; i < edges.size(); i++) {  
6:        graph[edges[i].first].push_back(edges[i].second);  
7:        graph[edges[i].second].push_back(edges[i].first);  
8:      }  
9:      vector<bool> visited(n);  
10:      int count = 0;  
11:      for (int i = 0; i < n; i++) {  
12:        if (!visited[i]) {  
13:          dfs(graph, visited, i);  
14:          count++;  
15:        }  
16:      }  
17:      return count;  
18:    }  
19:    void dfs(vector<vector<int>> &graph, vector<bool> &visited, int i) {  
20:      visited[i] = true;  
21:      for (int j = 0; j < graph[i].size(); j++) {  
22:        if (!visited[graph[i][j]]) {  
23:          dfs(graph, visited, graph[i][j]);  
24:        }  
25:      }  
26:    }  
27:  };