minimize-malware-spread-ii.py

# Time:  O(n^2)
# Space: O(n)

import collections


class UnionFind(object):
    def __init__(self, n):
        self.set = range(n)

    def find_set(self, x):
        if self.set[x] != x:
            self.set[x] = self.find_set(self.set[x])  # path compression.
        return self.set[x]

    def union_set(self, x, y):
        x_root, y_root = map(self.find_set, (x, y))
        if x_root == y_root:
            return False
        self.set[min(x_root, y_root)] = max(x_root, y_root)
        return True


class Solution(object):
    def minMalwareSpread(self, graph, initial):
        """
        :type graph: List[List[int]]
        :type initial: List[int]
        :rtype: int
        """
        initial_set = set(initial)
        clean = [i for i in xrange(len(graph)) if i not in initial_set]
        union_find = UnionFind(len(graph))
        for i in xrange(len(clean)):
            for j in xrange(i+1, len(clean)):
                if graph[clean[i]][clean[j]] == 1:
                    union_find.union_set(clean[i], clean[j])
        union_size = collections.Counter(union_find.find_set(i) for i in xrange(len(graph)))
        
        shared_union = collections.defaultdict(set)
        for i in initial:
            for j in clean:                  
                if graph[i][j] == 1:
                    x = union_find.find_set(j)
                    shared_union[x].add(i)

        result, total = float("inf"), float("-inf")
        for i in initial:
            lookup = set()
            curr = 0
            for j in clean:                  
                if graph[i][j] == 1:
                    x = union_find.find_set(j)
                    if len(shared_union[x]) == 1 and \
                       x not in lookup:
                        curr += union_size[x]
                        lookup.add(x)
            if curr > total or \
               (curr == total and i < result):
                total = curr
                result = i
        return result