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:  };  

368. Largest Divisible Subset

I don't have any clue to solve this problem. I followed one of the top voted solutions. The trick here is for a new integer I, it can be placed into the set as long as it divides the smallest number in the set or it can be divided by the largest number in the set. Also for the numbers in the same subset, we use union find solution.
Let T[n] be the size of the largest divisible subset whose largest number is nums[n].
Let child[n] be the index of its child in the nums[n].
Now let's look at an example, nums = [1,2,3,4].
i = 0, j = 0, T = [1,0,0,0] child=[0,0,0,0]
i = 1, j = 1, T = [1,1,0,0] child=[0,1,0,0]
         j = 0, T = [1,2,0,0] child=[0,0,0,0] (2's child is 1)
i = 2, j = 2, T = [1,2,1,0] child=[0,1,2,0]
         j = 1, 3 can't be divided by 2, nothing to change
         j = 0, T = [1,2,2,0] child=[0,0,0,0] (3's child is 1)
i = 3, j = 3, T = [1,2,2,1] child=[0,1,2,3]
         j = 2, 4 can't be divided by 3, nothing to change
         j = 1, T = [1,2,2,3] child=[0,1,2,1] (4's child is 2)
So far, the longest subset is 3. And we can find these three numbers by chasing the child[] array, i.e. nums[3]->nums[1]->nums[0] (i.e. 4,2,1). Therefore, in order to get the largest divisible subset, we can maintain the largest size of the subsets and the largest number's index in the set. The subset can be achieved by chasing the child[] array.

1:  class Solution {  
2:  public:  
3:    vector<int> largestDivisibleSubset(vector<int>& nums) {  
4:      vector<int> res;  
5:      if (nums.size() == 0) return res;  
6:      vector<int> T(nums.size(), 0);  
7:      vector<int> child(nums.size(), 0);  
8:      int m = 0, mi = 0;  
9:      sort(nums.begin(), nums.end());  
10:      for (int i = 0; i < nums.size(); i++) {  
11:        for (int j = i; j >= 0; j--) {  
12:          if (nums[i] % nums[j] == 0 && T[j] + 1 > T[i]) {  
13:            T[i] = T[j] + 1;  
14:            child[i] = j;  
15:          }  
16:          if (T[i] > m) {  
17:            m = T[i];  
18:            mi = i;  
19:          }  
20:        }  
21:      }  
22:      for (int i = 0; i < m; i++) {  
23:        res.push_back(nums[mi]);  
24:        mi = child[mi];  
25:      }  
26:      return res;  
27:    }  
28:  };  

305. Number of Islands II

There is a good video talking about Union Find for dynamic connectivity problem.
https://www.youtube.com/watch?v=dxONo9jDbN8
And here is its improvement.
https://www.youtube.com/watch?v=SpqjfGTOriQ
The idea is, check each pointer and its neighbors. If the neighbor is water, then do nothing. Otherwise, find the roots for node itself and the neighbor. If they don’t have the same parent, then do union.

When I revisited the problem, I made mistake in
line 11&16: I computed the index by "i * m + j".
line 17&19: I ignored when the neighbor isn't water and union the islands when two islands is connected (Really don't know what I was thinking...).

1:  class Solution {  
2:  public:  
3:    vector<int> numIslands2(int m, int n, vector<pair<int, int>>& positions) {  
4:      vector<int> res;  
5:      if (n == 0 || n == 0) return res;  
6:      vector<int> roots(m * n, -1);  
7:      vector<pair<int, int>> dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};  
8:      int count = 0;  
9:      for (int k = 0; k < positions.size(); k++) {  
10:        count++;  
11:        int r = positions[k].first * n + positions[k].second;  
12:        roots[r] = r;  
13:        for (int l = 0; l < 4; l++) {  
14:          int i = positions[k].first + dir[l].first;  
15:          int j = positions[k].second + dir[l].second;  
16:          int nr = i * n + j;  
17:          if (i < 0 || i == m || j < 0 || j == n || roots[nr] == -1) continue;  
18:          int r1 = findIslands(roots, nr), r2 = findIslands(roots, r);  
19:          if (r1 != r2) {  
20:            count--;  
21:            roots[r1] = r2; // union the two islands  
22:          }  
23:        }  
24:        res.push_back(count);  
25:      }  
26:      return res;  
27:    }  
28:    int findIslands(vector<int> &roots, int id) {  
29:      while (roots[id] != id) {  
30:        // path compression: make every other node to point to its grandparent  
31:        roots[id] = roots[roots[id]];   
32:        id = roots[id];  
33:      }  
34:      return id;  
35:    }  
36:  };  

128. Longest Consecutive Sequence

The idea is to set up a hashmap for all numbers first. And then scan all numbers again and try to find the first number that is not consecutive, i.e. nums[i]-1 is not in the hashmap. After that, count the consecutive numbers from that number on, and save the largest length until now.

1:  class Solution {  
2:  public:  
3:    int longestConsecutive(vector<int>& nums) {  
4:      unordered_map<int, int> mapping;  
5:      int maxLen = 0;  
6:      for (int i = 0; i < nums.size(); i++) {  
7:        mapping[nums[i]] = 1;  
8:      }  
9:      for (int i = 0; i < nums.size(); i++) {  
10:        if (mapping.find(nums[i]-1) == mapping.end()) {  
11:          int n = nums[i]+1;  
12:          while (mapping.find(n) != mapping.end()) {  
13:            n++;  
14:          }  
15:          maxLen = max(maxLen, n-nums[i]);  
16:        }  
17:      }  
18:      return maxLen;  
19:    }  
20:  };