✅✅ || C++ || UNION-FIND || Well Commented || Easy to Understand || ✅✅
\nclass Solution {\npublic:\n    \n    vector<int> parent;\n    vector<int> Size;\n    \n    int findParent(int x) {\n        if(parent[x] == x)\n            re
```\nclass Solution {\npublic:\n    \n    vector<int> parent;\n    vector<int> Size;\n    \n    int findParent(int x) {\n        if(parent[x] == x)\n            return x;\n        \n        return parent[x] = findParent(parent[x]);\n    }\n    \n    //We are not defining rank here as usual as we want the size \n    //of a particular group so whenever we merge we increment the size of its parent\n    void Union(int u, int v) {\n        if(Size[u] == Size[v]) {\n            parent[u] = v;\n            Size[v]++;\n        }\n        else if(Size[u] > Size[v]) {\n            parent[v] = u;\n            Size[u]++;\n        }\n        else if(Size[u] < Size[v]) {\n            parent[u] = v;\n            Size[v]++;\n        }\n    }\n    \n    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {\n        //initially we would not union nodes which are from initial vector\n        int n = graph.size();\n        \n        parent.resize(n);\n        Size.resize(n,1);\n        \n        for(int i=0; i<n; i++) {\n            parent[i] = i;\n        }\n        \n        //set to store infected nodes\n        set<int> st;\n        for(auto e : initial) {\n            st.insert(e);\n        }\n        \n        //build the components\n        for(int i=0; i<n; i++) {\n            for(int j=0; j<n; j++) {\n                if(graph[i][j] == 1 and find(st.begin(),st.end(),i) == st.end() and \n                  find(st.begin(),st.end(),j) == st.end()) {\n                    int p1 = findParent(i);\n                    int p2 = findParent(j);\n                    \n                    if(p1 != p2) {\n                        Union(p1,p2);\n                    }\n                }\n            }\n        }\n        \n        //now for every infected node we will store the corresponding neighbours\'s leader\n        //of the group \n        unordered_map<int,set<int>> map;\n        \n        //make an infected vector to see if a particular group has more than 1 infected nodes\n        //as in that case the removal of the node would be useless as the other node\n        //would infect the others\n        \n        //also while removing nodes we should consider that by removal of one infected node\n        //we do not remove another infected nodes which is possible when two infected nodes\n        //are neighbours (it would violate that we have to remove only one infected node)\n        \n        vector<int> infected(n);\n        \n        for(auto u : initial) {\n            for(int j=0; j<n; j++) {\n                if(graph[u][j] == 1 and u != j and find(st.begin(),st.end(),j) == st.end()) {\n                    int p = findParent(j);\n                    //the map should not be having the parent already \n                    if(find(map[u].begin(),map[u].end(),p) == map[u].end()) {\n                        map[u].insert(p);\n                        infected[p]++;\n                    }\n                }\n            }\n        }\n        \n        int ans = -1;\n        int maxi = -1;\n        \n        for(int u : initial) {\n            set<int> pars = map[u];\n            \n            int total = 0;\n            \n            for(auto p : pars) {\n                //only those groups having 1 infected node will be considered\n                if(infected[p] == 1) {\n                    total += Size[p];\n                }\n            }\n            \n            if(total >= maxi) {\n                if(total == maxi) {\n                    ans = min(ans,u);\n                }\n                else {\n                    ans = u;\n                }\n                maxi = total;\n            }\n        }\n        if(ans == -1) {\n            int mini = INT_MAX;\n            for(auto e : initial) {\n                mini = min(mini,e);\n            }\n            return mini;\n        }\n        return ans;\n    }\n};\n\n```
['Union Find', 'C']