0924 added.

liuyubobobo · liuyubobobo · commit aee1dbfaebf6 · 2018-10-16T18:27:14.000-07:00
diff --git a/0924-Minimize-Malware-Spread/cpp-0924/CMakeLists.txt b/0924-Minimize-Malware-Spread/cpp-0924/CMakeLists.txt
@@ -0,0 +1,7 @@
+cmake_minimum_required(VERSION 3.5)
+project(D)
+
+set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -std=c++11")
+
+set(SOURCE_FILES main2.cpp)
+add_executable(D ${SOURCE_FILES})
diff --git a/0924-Minimize-Malware-Spread/cpp-0924/main.cpp b/0924-Minimize-Malware-Spread/cpp-0924/main.cpp
@@ -0,0 +1,58 @@
+/// Source : https://leetcode.com/problems/minimize-malware-spread/description/
+/// Author : liuyubobobo
+/// Time   : 2018-10-13
+
+#include <iostream>
+#include <vector>
+#include <unordered_set>
+
+using namespace std;
+
+
+/// DFS
+/// Time Complexity: O(n^2)
+/// Space Complexity: O(n)
+class Solution {
+
+private:
+    int n;
+
+public:
+    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
+
+        unordered_set<int> init_set;
+        for(int e: initial)
+            init_set.insert(e);
+
+        n = graph.size();
+        vector<bool> visited(n, false);
+
+        int best = 0, res = -1;
+        for(int v = 0; v < n; v ++)
+            if(init_set.count(v)){
+                int cnt = dfs(graph, v, visited);
+                if(cnt > best){
+                    best = cnt;
+                    res = v;
+                }
+            }
+        return res;
+    }
+
+private:
+    int dfs(const vector<vector<int>>& g, int v, vector<bool>& visited){
+
+        visited[v] = true;
+        int res = 1;
+        for(int next = 0; next < n; next ++)
+            if(g[v][next] && !visited[next])
+                res += dfs(g, next, visited);
+        return res;
+    }
+};
+
+
+int main() {
+
+    return 0;
+}
diff --git a/0924-Minimize-Malware-Spread/cpp-0924/main2.cpp b/0924-Minimize-Malware-Spread/cpp-0924/main2.cpp
@@ -0,0 +1,83 @@
+/// Source : https://leetcode.com/problems/minimize-malware-spread/description/
+/// Author : liuyubobobo
+/// Time   : 2018-10-16
+
+#include <iostream>
+#include <vector>
+#include <unordered_set>
+
+using namespace std;
+
+
+/// Using Union-Find
+/// Time Complexity: O(n^2)
+/// Space Complexity: O(n)
+class UF{
+
+private:
+    vector<int> parent, sz;
+
+public:
+    UF(int n){
+        parent.clear();
+        for(int i = 0 ; i < n ; i ++){
+            parent.push_back(i);
+            sz.push_back(1);
+        }
+    }
+
+    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 minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
+
+        int n = graph.size();
+        UF uf(n);
+        for(int i = 0; i < n; i ++)
+            for(int j = i + 1; j < n; j ++)
+                if(graph[i][j])
+                    uf.unionElements(i, j);
+
+        sort(initial.begin(), initial.end());
+        int best = 0, res = -1;
+        for(int v: initial)
+            if(uf.size(v) > best){
+                best = uf.size(v);
+                res = v;
+            }
+        return res;
+    }
+};
+
+
+int main() {
+
+    return 0;
+}
diff --git a/readme.md b/readme.md
@@ -568,4 +568,4 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
 | 921 | [Minimum Add to Make Parentheses Valid](https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/description/) | [solution](https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/solution/) | [C++](0921-Minimum-Add-to-Make-Parentheses-Valid/cpp-0921/) | | |
 | 922 | [Sort Array By Parity II](https://leetcode.com/problems/sort-array-by-parity-ii/description/) | [solution](https://leetcode.com/problems/sort-array-by-parity-ii/solution/) | [C++](0922-Sort-Array-By-Parity-II/cpp-0922/) | | |
 | 923 | [3Sum With Multiplicity](https://leetcode.com/problems/3sum-with-multiplicity/description/) | [solution](https://leetcode.com/problems/3sum-with-multiplicity/solution/) | [C++](0923-3Sum-With-Multiplicity/cpp-0923/) | | |
-| | | | | | |
+| 924 | [Minimize Malware Spread](https://leetcode.com/problems/minimize-malware-spread/description/) | [solution](https://leetcode.com/problems/minimize-malware-spread/solution/) | [C++](0924-Minimize-Malware-Spread/cpp-0924/) | | |
