Untitled

mail@pastecode.io avatar
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];
    }
};