Easy to understand | DFS
\nclass Group{\n    public:\n    \n    set<pair<int,int>>ne;\n    set<pair<int,int>>affected;\n    \n    int w;\n    \n    Group(){\n        w = 0;\n    }\n};\n
```\nclass Group{\n    public:\n    \n    set<pair<int,int>>ne;\n    set<pair<int,int>>affected;\n    \n    int w;\n    \n    Group(){\n        w = 0;\n    }\n};\n\n\n\nclass Solution {\npublic:\n    \n    bool isValid(int i,int j,int n,int m){\n        return i>=0 && j>=0 && i<n && j<m;\n    }\n    \n    int dir[4][2]={\n        {1,0},\n        {0,1},\n        {-1,0},\n        {0,-1}\n    };\n    \n\n    void dfs(vector<vector<int>>&in,int i,int j,int n,int m,vector<vector<bool>>&vis,Group *g){\n        \n        if(in[i][j]==-1) return;\n        \n        if(in[i][j] ==0 ){\n            g->w++;\n            g->ne.insert({i,j});\n            return;\n        }\n        \n        vis[i][j] = 1;\n        \n        if(in[i][j] == 1)\n            g->affected.insert({i,j});\n           \n        \n        for(int k=0;k<4;k++){\n            \n            int x = i+dir[k][0], y = j+dir[k][1];\n            \n            if(isValid(x,y,n,m) && !vis[x][y]) \n                dfs(in,i+dir[k][0],j+dir[k][1],n,m,vis,g);\n        }\n        \n    }\n    \n    \n    int containVirus(vector<vector<int>>& in) {\n        \n        int n = in.size(),m = in[0].size(),ans = 0;\n        \n        \n        while(1){\n            \n            vector<Group *>v;\n            \n            vector<vector<bool>>visited(n,vector<bool>(m,0));\n            \n            for(int i=0;i<n;i++){\n                for(int j=0;j<m;j++){\n                    if(!visited[i][j] && in[i][j]==1){\n                        \n                        Group *g  = new Group();\n                        dfs(in,i,j,n,m,visited,g);\n                        \n                        v.push_back(g);\n                    }\n                        \n                }\n            }\n            \n            \n            if(v.size()==0) break;\n            \n            \n            int mx = 0,index = 0;\n            \n            for(int i=0;i<v.size();i++){\n                if(v[i]->ne.size()>mx){\n                    mx = v[i]->ne.size();\n                    index = i;\n                }\n            }\n            \n            Group * x = v[index];\n            \n            ans+=(x->w);\n            \n            \n            for(auto itr:x->affected){\n                in[itr.first][itr.second] = -1;\n            }\n            \n            \n            for(int i=0;i<v.size();i++){\n                if(i==index) continue;\n                x = v[i];\n                for(auto itr:x->ne){\n                    in[itr.first][itr.second] = 1;\n                }\n                \n            }\n            \n \n        }\n        \n        return ans;\n    }\n};\n```
['Depth-First Search', 'C']