using disjoint union
\n\n# Code\ncpp []\nclass Solution {\npublic:\n    int Uparent(int u,vector<int>& parent){\n        if(u==parent[u])\n            return u;\n        return pare
\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int Uparent(int u,vector<int>& parent){\n        if(u==parent[u])\n            return u;\n        return parent[u]=Uparent(parent[u],parent);\n    }\n    void union_disjoint(int u,int v,vector<int>& parent,vector<int>& size){\n        int pu=Uparent(u,parent);\n        int pv=Uparent(v,parent);\n\n        if(pu==pv)\n            return;\n        if(size[pv]>size[pu]){\n            parent[pu]=pv;\n            size[pv]+=size[pu];\n        }\n        else{\n            parent[pv]=pu;\n            size[pu]+=size[pv];\n        }\n    }\n    bool valid(int i,int j,int n,int m){\n        return i>=0 && j>=0 && i<n && j<m;\n    }\n    int containVirus(vector<vector<int>>& isInfected) {\n        int n=isInfected.size();\n        int m=isInfected[0].size();\n        int total=n*m;\n        int totalWalls=0;\n        \n        vector<int> x={0,1,0,-1};\n        vector<int> y={1,0,-1,0};\n\n        \n        while(true){\n            vector<int> parent(n*m);\n            vector<int> size(n*m,1);\n            for(int i=0;i<n*m;i++){\n                parent[i]=i;\n            }    \n            for(int i=0;i<n;i++){\n                for(int j=0;j<m;j++){\n                    if(isInfected[i][j]==1){\n\n                        for(int k=0;k<4;k++){\n                            int newx=i+x[k];\n                            int newy=j+y[k];\n\n                            if(valid(newx,newy,n,m) && isInfected[newx][newy]==1){\n                                union_disjoint(i*m+j,newx*m+newy,parent,size);\n                            }\n                        }\n                    }\n                }\n            }\n\n            vector<unordered_set<int>> threats(n * m);\n            vector<int> walls(n * m, 0);\n\n            for(int i=0;i<n;i++){\n                for(int j=0;j<m;j++){\n                    if(isInfected[i][j]==1){\n                        int root=Uparent(i*m+j,parent);\n                        for(int k=0;k<4;k++){\n                            int newx=i+x[k];\n                            int newy=j+y[k];\n\n                            if(valid(newx,newy,n,m) && isInfected[newx][newy]==0){\n                                threats[root].insert(newx*m+newy);\n                                walls[root]++;\n                            }\n                        }\n                    }\n                }\n            }\n            int maxThreat=0;\n            int maxThreatCluster=-1;\n\n            for(int i=0;i<n*m;i++){\n                if(!threats[i].empty() && threats[i].size()>maxThreat){\n                    maxThreat=threats[i].size();\n                    maxThreatCluster=i;\n                }\n            }\n\n            if(maxThreatCluster==-1) break;\n            \n            totalWalls+=walls[maxThreatCluster];\n            for(int i=0;i<n;i++){\n                for(int j=0;j<m;j++){\n                    if(isInfected[i][j]==1 && Uparent(i*m+j,parent)==maxThreatCluster){\n                        isInfected[i][j]=-1;\n                    }\n                }\n            }\n\n            for (int i = 0; i < n; i++) {\n                for (int j = 0; j < m; j++) {\n                    if (isInfected[i][j] == 1) {\n                        int root = Uparent(i * m + j, parent);\n                        if (root != maxThreatCluster) {\n                            for (int k : threats[root]) {\n                                isInfected[k / m][k % m] = 1; \n                            }\n                        }\n                    }\n                }\n            }\n        }\n        return totalWalls;\n    }\n};\n```
['C++']