928. Minimize Malware Spread II.cpp
Code\n\nclass UnionFind {\npublic: \n    vector<int> parent, rank; \n    UnionFind(int n) {\n        parent.resize(n); \n        iota(parent.begin(), parent.end
**Code**\n```\nclass UnionFind {\npublic: \n    vector<int> parent, rank; \n    UnionFind(int n) {\n        parent.resize(n); \n        iota(parent.begin(), parent.end(), 0); \n        rank = vector<int>(n, 1); \n    }    \n    int find(int p) {\n        if (p != parent[p]) \n            parent[p] = find(parent[p]); \n        return parent[p]; \n    }    \n    bool connect(int p, int q) {\n        int prt = find(p), qrt = find(q); \n        if (prt == qrt) return false; \n        if (rank[prt] > rank[qrt]) swap(prt, qrt); \n        parent[prt] = qrt; \n        rank[qrt] += rank[prt]; \n        return true; \n    }\n}; \nclass Solution {\npublic:\n    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {\n        int n = graph.size(); \n        vector<bool> infect(n, false); \n        for (auto& x : initial) infect[x] = true;         \n        UnionFind* uf = new UnionFind(n); \n        for (int u = 0; u < n; ++u) \n            if (!infect[u]) \n                for (int v = 0; v < n; ++v) \n                    if (!infect[v] && graph[u][v]) \n                        uf->connect(u, v);         \n        unordered_map<int, unordered_set<int>> mp; \n        for (auto& u : initial) \n            for (int v = 0; v < n; ++v) \n                if (!infect[v] && graph[u][v]) \n                    mp[u].insert(uf->find(v));         \n        unordered_map<int, int> freq; \n        for (auto& [k, v] : mp) \n            for (auto& x : v) ++freq[x];         \n        int best = -1, ans = -1; \n        for (auto& u : initial) {\n            int cnt = 0; \n            for (auto& v : mp[u]) \n                if (freq[v] == 1) cnt += uf->rank[v]; \n            if (cnt > best || (cnt == best && u < ans)) \n                ans = u, best = cnt; \n        }\n        return ans; \n    }\n};\n```
['C++']