0947 solved.

liuyubobobo · liuyubobobo · commit bd5f310a7223 · 2018-11-25T12:16:22.000-08:00
diff --git a/0947-Most-Stones-Removed-with-Same-Row-or-Column/cpp-0947/CMakeLists.txt b/0947-Most-Stones-Removed-with-Same-Row-or-Column/cpp-0947/CMakeLists.txt
@@ -0,0 +1,6 @@
+cmake_minimum_required(VERSION 3.12)
+project(C)
+
+set(CMAKE_CXX_STANDARD 11)
+
+add_executable(C main2.cpp)
diff --git a/0947-Most-Stones-Removed-with-Same-Row-or-Column/cpp-0947/main.cpp b/0947-Most-Stones-Removed-with-Same-Row-or-Column/cpp-0947/main.cpp
@@ -0,0 +1,65 @@
+/// Source : https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/
+/// Author : liuyubobobo
+/// Time   : 2018-11-25
+
+#include <iostream>
+#include <vector>
+#include <unordered_set>
+
+using namespace std;
+
+
+/// Using DFS to calculate connected components
+/// Time Complexity: O(n)
+/// Space Complexity: O(n)
+class Solution {
+public:
+    int removeStones(vector<vector<int>>& stones) {
+
+        int n = stones.size();
+        vector<unordered_set<int>> g(n);
+        for(int i = 0; i < n; i ++)
+            for(int j = i + 1; j < n; j ++)
+                if(stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1]){
+                    g[i].insert(j);
+                    g[j].insert(i);
+                }
+
+        int res = 0;
+        vector<bool> visited(n, false);
+        for(int i = 0; i < n; i ++)
+            if(!visited[i])
+                res += dfs(g, i, visited) - 1;
+
+        return res;
+    }
+
+private:
+    int dfs(const vector<unordered_set<int>> &g, int v, vector<bool> &visited){
+
+        visited[v] = true;
+        int res = 1;
+        for(int next: g[v])
+            if(!visited[next])
+                res += dfs(g, next, visited);
+        return res;
+    }
+};
+
+
+int main() {
+
+    vector<vector<int>> stones1 = {{0,0},{0,1},{1,0},{1,2},{2,1},{2,2}};
+    cout << Solution().removeStones(stones1) << endl;
+    // 5
+
+    vector<vector<int>> stones2 = {{0,0},{0,2},{1,1},{2,0},{2,2}};
+    cout << Solution().removeStones(stones2) << endl;
+    // 3
+
+    vector<vector<int>> stones3 = {{0,0}};
+    cout << Solution().removeStones(stones3) << endl;
+    // 0
+
+    return 0;
+}
diff --git a/0947-Most-Stones-Removed-with-Same-Row-or-Column/cpp-0947/main2.cpp b/0947-Most-Stones-Removed-with-Same-Row-or-Column/cpp-0947/main2.cpp
@@ -0,0 +1,94 @@
+/// Source : https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/
+/// Author : liuyubobobo
+/// Time   : 2018-11-25
+
+#include <iostream>
+#include <vector>
+#include <unordered_set>
+
+using namespace std;
+
+
+/// Using Union-Find to calculate connected components
+/// Time Complexity: O(n)
+/// Space Complexity: O(n)
+class UF{
+
+private:
+    vector<int> parent, sz;
+
+public:
+    UF(int n): sz(n, 1){
+        for(int i = 0 ; i < n ; i ++)
+            parent.push_back(i);
+    }
+
+    int find(int p){
+        if(p != parent[p])
+            parent[p] = find(parent[p]);
+        return parent[p];
+    }
+
+    bool isConnected(int p , int q){
+        return find(p) == find(q);
+    }
+
+    void unionElements(int p, int q){
+
+        int pRoot = find(p);
+        int qRoot = find(q);
+
+        if( pRoot == qRoot )
+            return;
+
+        parent[pRoot] = qRoot;
+        sz[qRoot] += sz[pRoot];
+    }
+
+    int size(int p){
+        return sz[find(p)];
+    }
+};
+
+class Solution {
+public:
+    int removeStones(vector<vector<int>>& stones) {
+
+        int n = stones.size();
+        UF uf(n);
+        for(int i = 0; i < n; i ++)
+            for(int j = i + 1; j < n; j ++)
+                if(stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1])
+                    uf.unionElements(i, j);
+
+        int res = 0;
+        unordered_set<int> groups;
+        for(int i = 0; i < n; i ++){
+            int group = uf.find(i);
+            if(!groups.count(group)){
+                res += uf.size(i) - 1;
+                groups.insert(group);
+            }
+        }
+
+        return res;
+    }
+};
+
+
+int main() {
+
+    vector<vector<int>> stones1 = {{0,0},{0,1},{1,0},{1,2},{2,1},{2,2}};
+    cout << Solution().removeStones(stones1) << endl;
+    // 5
+
+    vector<vector<int>> stones2 = {{0,0},{0,2},{1,1},{2,0},{2,2}};
+    cout << Solution().removeStones(stones2) << endl;
+    // 3
+
+    vector<vector<int>> stones3 = {{0,0}};
+    cout << Solution().removeStones(stones3) << endl;
+    // 0
+
+    return 0;
+}
diff --git a/readme.md b/readme.md
@@ -603,4 +603,5 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
 | 944 | [Delete Columns to Make Sorted](https://leetcode.com/problems/delete-columns-to-make-sorted/) | [solution](https://leetcode.com/problems/delete-columns-to-make-sorted/solution/) | [C++](0944-Delete-Columns-to-Make-Sorted/cpp-0944/) | | |
 | 945 | [Minimum Increment to Make Array Unique](https://leetcode.com/problems/minimum-increment-to-make-array-unique/) | [solution](https://leetcode.com/problems/minimum-increment-to-make-array-unique/solution/) | [C++](0945-Minimum-Increment-to-Make-Array-Unique/cpp-0945/) | | |
 | 946 | [Validate Stack Sequences](https://leetcode.com/problems/validate-stack-sequences/) | [solution](https://leetcode.com/problems/validate-stack-sequences/solution/) | [C++](0946-Validate-Stack-Sequences/cpp-0946/) | | |
+| 947 | [Most Stones Removed with Same Row or Column](https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/) | [solution](https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/solution/) | [C++](0947-Most-Stones-Removed-with-Same-Row-or-Column/cpp-0947/) | | |
 | | | | | | |
