main2.cpp

/// Source : https://leetcode.com/problems/minimize-malware-spread/description/
/// Author : liuyubobobo
/// Time   : 2018-10-16

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;


/// Using Union-Find
/// Time Complexity: O(n^2)
/// Space Complexity: O(n)
class UF{

private:
    vector<int> parent, sz;

public:
    UF(int n){
        parent.clear();
        for(int i = 0 ; i < n ; i ++){
            parent.push_back(i);
            sz.push_back(1);
        }
    }

    int find(int p){
        if( p != parent[p] )
            parent[p] = find( parent[p] );
        return parent[p];
    }

    bool isConnected(int p , int q){
        return find(p) == find(q);
    }

    void unionElements(int p, int q){

        int pRoot = find(p);
        int qRoot = find(q);

        if( pRoot == qRoot )
            return;

        parent[pRoot] = qRoot;
        sz[qRoot] += sz[pRoot];
    }

    int size(int p){
        return sz[find(p)];
    }
};

class Solution {

public:
    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {

        int n = graph.size();
        UF uf(n);
        for(int i = 0; i < n; i ++)
            for(int j = i + 1; j < n; j ++)
                if(graph[i][j])
                    uf.unionElements(i, j);

        sort(initial.begin(), initial.end());
        int best = 0, res = -1;
        for(int v: initial)
            if(uf.size(v) > best){
                best = uf.size(v);
                res = v;
            }
        return res;
    }
};


int main() {

    return 0;
}