Untitled
unknown
plain_text
a year ago
994 B
2
Indexable
Never
class Solution { public: vector<int> par; int find(int v){ if(v!= par[v]) par[v]=find(par[v]); return par[v]; } void uni(int a,int b){ par[find(a)]=find(b); } int minMalwareSpread(vector<vector<int>>& graph, vector<int>& in) { int n=graph.size(); vector<int> area(n,0); vector<int> malware(n,0); for(int i=0;i<n;i++) par.push_back(i); for(int i=0;i<n;i++){ for(int j=i+1;j<n;j++){ if(graph[i][j]) uni(i,j); } } for(int i=0;i<n;i++) area[find(i)]++; //area of each union set for(auto i:in) malware[find(i)]++; //no of malware in each union set vector<int> res= {1,0}; for(auto i:in) { res =min(res, {(malware[find(i)]==1) * -area[find(i)],i}); //if malware[find(i)] is greater than 1 then if we remove i we only get one less infected element } return res[1]; } };