Two Approaches one DFS and  another Union Find | c++ | EASY to Understand
Intuition\nFor a infected node do  dfs traversal to  get all infected nodes finally.\n\n# Approach\nFor each node in initial vector don\'t do dfs tarversal and 
# Intuition\nFor a infected node do  dfs traversal to  get all infected nodes finally.\n\n# Approach\nFor each node in initial vector don\'t do dfs tarversal and do for other infected initial nodes so all the nodes which are in same component can marked as visited . So it means that all nodes which are marked as visited will get infected if this one infected node is removed.\n\n# Complexity\n- Time complexity:\n$$O(n*m)$$  N is for dfs Traversal and M is for traversing through initial vector and for each node in intial vector dfs function is called.  \n\n- Space complexity:\n$$O(n^2)$$  It is for storing graph as adjacency list.\n\n\n# Code\n```\nvoid dfs(int node,vector<int>&vis, vector<vector<int>> &adj,int block)\n{\n    vis[node]=1;\n    for(auto it:adj[node])\n    {\n        if(vis[it]==0 && it!=block)\n        {\n            dfs(it,vis,adj,block);\n        }\n    }\n}\nclass Solution {\npublic:\n    int minMalwareSpread(vector<vector<int>>& g, vector<int>& ini) {\n\n        int n=g.size();\n        int m=ini.size();\n        vector<vector<int>> adj(n);\n        for(int i=0;i<n;++i)\n        {\n            for(int j=0;j<n;++j)\n            {\n                if(g[i][j]==1)\n                {\n                    adj[i].push_back(j);\n                }\n            }\n        }\n        sort(ini.begin(),ini.end());\n        int ans;\n        int mini=1e9;\n        for(int k=0;k<m;++k)\n        {\n\n            vector<int> vis(n,0);\n            for(int j=0;j<m;++j)\n            {\n                if(j!=k)\n                {\n                    if(vis[ini[j]]==0)\n                    dfs(ini[j],vis,adj,ini[k]);\n                }\n            }\n            int tot=0;\n            for(int i=0;i<n;++i)\n            {\n                if(vis[i]==1) tot++;\n            }\n\n            if(mini>tot)\n            {\n                ans=ini[k];\n                mini=tot;\n            }\n\n        }\n\n        return ans;\n        \n    }\n};\n```\n\n# Intuition\nUnite all nodes which can be infected and then get all nodes which are infected by getting size of that component using union by size.\n\n\n# Complexity\n- Time complexity:\n$$O(n*n*m)$$ \n\n- Space complexity:\n$$O(n)$$ \n\n# Code\n```\nclass DSU{\n\n    public:\n    vector<int> p,si;\n\n    DSU(int n)\n    {\n        p.resize(n+1);\n        for(int i=0;i<=n;++i) p[i]=i;\n        si.resize(n+1,1);\n    }\n\n    int fp(int n)\n    {\n        if(n==p[n]) return n;;\n\n        return p[n]=fp(p[n]);\n    }\n\n    void  union1(int u,int v)\n    {\n        int pu=fp(u);\n        int pv=fp(v);\n\n        if(pu==pv) return ;\n\n        if(si[pu]>si[pv])\n        {\n            si[pu]+=si[pv];\n            p[pv]=pu;\n        }\n        else\n        {\n            si[pv]+=si[pu];\n            p[pu]=pv;           \n        }\n    }\n};\n\nclass Solution {\npublic:\n    int minMalwareSpread(vector<vector<int>>& g, vector<int>& ini) {\n\n        int n=g.size();\n        int m=ini.size();\n        sort(ini.begin(),ini.end());\n        int ans;\n        int mini=1e9;\n        for(int k=0;k<m;++k)\n        {\n            DSU ds(n);\n            for(int i=0;i<n;++i)\n            {\n                for(int j=0;j<n;++j)\n                {\n                    if(g[i][j]==1)\n                    {\n                        if(!(i==ini[k] || j==ini[k]))\n                        ds.union1(i,j);\n                    }\n                }\n            }\n           \n            set<int> s;\n            for(int j=0;j<m;++j)\n            {\n                if(k!=j)\n                {\n                    s.insert(ds.fp(ini[j]));\n                }\n            }\n\n            int tot=0;\n            for(auto it:s)\n            {\n                tot+=ds.si[it];\n            }\n\n            if(mini>tot)\n            {\n                ans=ini[k];\n                mini=tot;\n            }\n\n        }\n\n        return ans;\n        \n    }\n};\n```
['C++']