C++| DFS+DSU
\nclass Solution {\npublic:\n    int n,m;\n    int d[4][2] = {{0,1},{1,0},{-1,0},{0,-1}};\n    int find(vector<int>& nums,int i){\n        if(nums[i]==-1) retur
```\nclass Solution {\npublic:\n    int n,m;\n    int d[4][2] = {{0,1},{1,0},{-1,0},{0,-1}};\n    int find(vector<int>& nums,int i){\n        if(nums[i]==-1) return i;\n        else return nums[i] = find(nums,nums[i]);\n    }\n    void union_(vector<int>& nums,int x,int y){\n        int i = find(nums,x), j = find(nums,y);\n        if(i!=j){\n            if(i<j) nums[j] = i;\n            else nums[i] = j;\n        }\n    }\n    int dfs(vector<vector<int>>& nums,int i,int j){  // returns no. of wall arround the infected region\n        if(nums[i][j]==0) return 1;\n        nums[i][j] = 2;\n        int re = 0;\n        for(int k = 0; k<4;++k){\n            int x = i+d[k][0], y = j+d[k][1];\n            if(!(x<0||x>=n||y<0||y>=m) && nums[x][y]!=2) re+=dfs(nums,x,y);\n        }\n        return re;\n    }\n    int dfs2(vector<vector<int>>& nums,vector<int>& dp,int p){  // returns no. of blocks going to infect in next 1 sec.\n        int re = 0;\n        for(int i = 0; i<n;++i){\n            for(int j = 0; j<m; ++j){\n                if(nums[i][j]!=0) continue;\n                for(int k = 0; k<4;++k){\n                    int x = i+d[k][0], y = j+d[k][1];\n                    if(!(x<0||x>=n||y<0||y>=m) && nums[x][y]==1 && p==find(dp,x*m+y)){\n                        re++; break;\n                    }\n                }\n            }\n        }\n        return re;\n    }\n    int containVirus(vector<vector<int>>& nums) {\n         n = nums.size(), m = nums[0].size();\n        vector<int> dp(n*m+1,-1);\n        for(int i = 0; i<n;++i){  // union all adjacent infected region\n            for(int j = 0; j<m; ++j){\n                if(nums[i][j]!=1) continue;\n                for(int k = 0; k<4;++k){\n                    int x = i+d[k][0], y = j+d[k][1];\n                    if(!(x<0||x>=n||y<0||y>=m) && nums[x][y]==1)\n                        union_(dp,i*m+j,x*m+y);\n                }\n            }\n        }\n        int re = 0;\n        while(1){\n            int p = -1,max_ = -1;\n            for(int k = 0; k<n*m;++k){  // find the region going to infect maximum uninfected region in next 1 sec.\n                int i = k/m; int j = k-i*m;\n                if(dp[k]==-1 && nums[i][j]==1){\n                    int t = dfs2(nums,dp,k);  // no. of uninfected going to infect in next 1 sec by some infect whose parent node if k.\n                    if(t>max_){\n                        max_ = t; p = k;\n                    }\n                }\n            }\n            if(p==-1) break; // break if there are no blocks to infect\n            int i = p/m; int j = p-i*m;\n            int tre = dfs(nums,i,j); // no. of wall\n            re+=tre;\n            vector<pair<int,int>> temp;\n            for(int i = 0; i<n;++i){  // infect the uninfected region in next sec.\n                for(int j = 0;j<m;++j){\n                    if(nums[i][j]!=0) continue;\n                    bool is= 0;\n                    for(int k = 0; k<4;++k){\n                        int x = i+d[k][0], y = j+d[k][1];\n                        if(!(x<0||x>=n||y<0||y>=m) && nums[x][y]==1) {is = 1; break;}\n                    }\n                    if(is) temp.push_back({i,j});\n                }\n            }\n            for(int i = 0; i<temp.size();++i) nums[temp[i].first][temp[i].second] = 1;  \n            for(int k = 0; k<temp.size(); ++k){  // union newly infected cells to there adjacent\n                int i = temp[k].first, j = temp[k].second;\n                for(int l = 0; l<4;++l){\n                    int x = i+d[l][0], y = j+d[l][1];\n                    if(!(x<0||x>=n||y<0||y>=m) && nums[x][y]==1) union_(dp,i*m+j,x*m+y);\n                } \n            }\n        }\n        return re;\n    }\n};\n// Try for larger TestCase\n// [[0,0,1,1,1,0,1,0,0,0],[1,1,1,0,0,0,1,1,0,1],[0,0,0,0,0,0,1,0,0,0],[0,0,0,0,1,0,1,0,0,0],[1,0,0,0,1,1,1,0,0,0],[0,0,0,1,0,1,1,0,0,0],[1,0,0,0,0,1,0,0,0,1],[1,0,0,0,0,0,0,0,0,1],[0,1,0,0,0,0,0,0,1,0],[1,1,0,0,0,1,0,1,0,0]]\n\n```
['Depth-First Search', 'C']