【Day 77 】2022-02-26 - 924. 尽量减少恶意软件的传播

[azl397985856]

924. 尽量减少恶意软件的传播

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/minimize-malware-spread

前置知识

暂无

题目描述

在节点网络中，只有当 graph[i][j] = 1 时，每个节点 i 能够直接连接到另一个节点 j。

一些节点 initial 最初被恶意软件感染。只要两个节点直接连接，且其中至少一个节点受到恶意软件的感染，那么两个节点都将被恶意软件感染。这种恶意软件的传播将继续，直到没有更多的节点可以被这种方式感染。

假设 M(initial) 是在恶意软件停止传播之后，整个网络中感染恶意软件的最终节点数。

我们可以从初始列表中删除一个节点。如果移除这一节点将最小化 M(initial)， 则返回该节点。如果有多个节点满足条件，就返回索引最小的节点。

请注意，如果某个节点已从受感染节点的列表 initial 中删除，它以后可能仍然因恶意软件传播而受到感染。

示例 1：

输入：graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
输出：0
示例 2：

输入：graph = [[1,0,0],[0,1,0],[0,0,1]], initial = [0,2]
输出：0
示例 3：

输入：graph = [[1,1,1],[1,1,1],[1,1,1]], initial = [1,2]
输出：1

提示：

1 < graph.length = graph[0].length <= 300
0 <= graph[i][j] == graph[j][i] <= 1
graph[i][i] == 1
1 <= initial.length < graph.length
0 <= initial[i] < graph.length

[yetfan]

思路 找并集。 从initial中，遍历每个节点，计算并集大小，找到集合出现次数为1的节点，对比集合大小，选出集合最大的 如果一直没找到，返回第一个节点。

代码

class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        n = len(graph)
        uf = UnionFind(n)
        for i in range(n):
            uf.add(i)
            for j in range(i):
                if graph[i][j]:
                    uf.merge(i,j)
        initial.sort()  # 整理顺序，这样只需要判断更大的集合，相同集合大小会自动选择数字小的
        once = [uf.find(i) for i in initial]

        # 找到出现一次的
        dic = {}
        for o in once:
            if o not in dic:
                dic[o] = True
            else:
                dic[o] = False

        a = [0, 0]
        for i, o in enumerate(once):
            if dic[o] == True:
                # 出现一次的节点们要比集合大小，选最大的那个
                size = uf.get_size(o)
                if size > a[1]:
                    a[0] = i
                    a[1] = size
        if a[1] > 0:
            return initial[a[0]]
        return min(initial)

class UnionFind:
    def __init__(self, n):
        self.father = {}
        self.size = [1] * n

    def find(self,x):
        root = x
        while self.father[root] != None:
            root = self.father[root]

        while x != root:
            original_father = self.father[x]
            self.father[x] = root
            x = original_father

        return root

    def merge(self,x,y):
        root_x,root_y = self.find(x),self.find(y)

        if root_x != root_y:
            self.size[root_y] += self.size[root_x]
            self.father[root_x] = root_y

    def add(self,x):
        if x not in self.father:
            self.father[x] = None

    def get_size(self, x):
        return self.size[self.find(x)]

复杂度 时间 O(n^2) 空间 O(n)

[QinhaoChang]

class UnionFind: def init(self, n: int): self.parent = list(range(n)) self.size = [1] * n self.n = n

当前连通分量数目

    self.setCount = n

def findset(self, x: int) -> int:
    if self.parent[x] == x:
        return x
    self.parent[x] = self.findset(self.parent[x])
    return self.parent[x]

def unite(self, x: int, y: int) -> bool:
    '''
    合并
    '''
    x, y = self.findset(x), self.findset(y)
    if x == y:
        return False
    if self.size[x] < self.size[y]:
        x, y = y, x
    self.parent[y] = x
    self.size[x] += self.size[y]
    self.setCount -= 1
    return True

def connected(self, x: int, y: int) -> bool:
    '''
    连通性
    '''
    x, y = self.findset(x), self.findset(y)
    return x == y

def isolate(self, x: int) -> None:
    '''
    孤立
    '''
    if self.parent[x] != x:
        self.parent[x] = x
        self.size[x] = 1
        self.setCount += 1

class Solution: def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int: n=len(graph) UF = UnionFind(n) for i in range(n-1): for j in range(i+1,n): if graph[i][j]: UF.unite(i,j) initial.sort() P=Counter() for i in initial: P[UF.parent[i]]+=1 isolated = [] for i in initial: if P[UF.parent[i]] == 1: isolated.append(i) if not isolated: return initial[0] else: ans = -1 maxsize = -1 for i in isolated: size = UF.size[UF.parent[i]] if size > maxsize: maxsize = size ans = i return ans

[feifan-bai]

思路 1.Union find

代码

class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        def dfs(i):
            nodes.add(i)
            for j in range(len(graph[i])):
                if graph[i][j] and j not in nodes:
                    dfs(j)
        rank, initial = collections.defaultdict(list), set(initial)
        for node in sorted(initial):
            nodes = set()
            dfs(node)
            if nodes & initial == {node}:
                rank[len(nodes)].append(node)
        return rank[max(rank)][0] if rank else min(initial)

复杂度分析

• 时间复杂度：O(N*N)
• 空间复杂度：O(N)

[zjsuper]

class Solution(object):
    def minMalwareSpread(self, graph, initial):
        def dfs(node,vis):
            for v in  range(len(graph[node])):
                if graph[node][v] == 1 and v not in vis:
                    vis.add(v)
                    dfs(v,vis)

        s = set(initial)
        t_vis = set()
        del_node, subgraph_len = min(initial), 0
        for node in range(len(graph)):
            if node not in t_vis:
                vis = set([node])
                dfs(node,vis)
                # caculate the number of infected node in the subgraph
                infect = vis & s
                if len(infect) == 1:
                    # more number of nodes or smaller index
                    if len(vis) > subgraph_len or (len(vis) == subgraph_len and list(infect)[0] < del_node):
                        del_node,subgraph_len = list(infect)[0],len(vis)
                t_vis |= vis
        return del_node

[wangzehan123]

• 语言支持：Java

Java Code:

class Solution {
    public int minMalwareSpread(int[][] graph, int[] initial) {
        int len = graph.length;
        UnionFind union = new UnionFind();
        union.init(len);
        for(int i = 0; i < len; i++) {
            for(int j = i+1; j < len; j++) {
                if(graph[i][j] == 1) {
                    union.merge(i, j);
                }
            }
        }
        // 如果有多个节点满足条件，就返回索引最小的节点。 因此需要先对 initial 排序
        Arrays.sort(initial);
        int res = initial[0];
        int max = 0; // 记录集合的联通块数最大的集合大小
        for(int i = 0; i < initial.length; i++) {
            int root = union.find(initial[i]);
            boolean notOnly = false;
            for(int j = 0; j < initial.length; j++) {
                if(i == j) {
                    continue;
                }
                if(union.find(initial[j]) == root) {
                    notOnly = true;
                    break;
                }
            }
            if(!notOnly) {
                int count = 0;
                for(int k = 0; k < len; k++) {
                    if(union.find(k) == root) {
                        count++;
                    }
                }
                // 此节点所属的联通块数是目前最大的集合，则更新 max 的值。
                if(count > max) {
                    max = count;
                    res = initial[i];
                }
            }
        }
        return res;
    }
    private class UnionFind {

        private int[] parent;
        private int[] rank; // 记录每个根节点对应的树的深度
        private void init(int len) {
            this.parent = new int[len];
            this.rank = new int[len];
            for(int i = 0; i < len; ++i) {
                parent[i] = i;
                rank[i] = 1;
            }
        }

        // 路径压缩  把沿途的每个节点的父节点都设为根节点
        private int find(int x) {
            return x == parent[x] ? parent[x] : (parent[x] = find(parent[x]));
        }

        private void merge(int x, int y) {
            int xroot = find(x); //先找到两个根节点
            int yroot = find(y);
            if(xroot == yroot) {
                return;
            }
            // 合并时比较两个根节点，把rank较小者往较大者上合并
            if(rank[xroot] <= rank[yroot]) {
                parent[xroot] = yroot;
            } else {
                parent[yroot] = xroot;
            }
            if(rank[xroot] == rank[yroot]) {
                rank[yroot]++; // //如果深度相同且根节点不同，则新的根节点的深度+1
            }
        }
    }
}

[callmeerika]

思路

并查集

代码

var City = function (n) {
  this.parent = {};
  this.size = {};
  this.init(n);
};

City.prototype.init = function (n) {
  for (let i = 0; i < n; i++) {
    this.parent[i] = i;
    this.size[i] = 1;
  }
};

City.prototype.find = function (x) {
  while (x != this.parent[x]) x = this.parent[x];
  return x;
};

City.prototype.union = function (x, y) {
  let xp = this.find(x);
  let yp = this.find(y);
  this.parent[xp] = yp;
  this.size[yp] += this.size[xp];
};

var minMalwareSpread = function(graph, initial) {
    const n = graph.length;
    const cnt = new Array(n).fill(0);
    const city = new City(n);
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
        if (graph[i][j] === 1) {
            city.union(i, j);
        }
        }
    }
    for (let node of initial) {
        let p = city.find(node)
         cnt[p] += 1;
    }
    let ans = -1;
    let ansSize = -1;
    for (let node of initial) {
        let root = city.find(node);
        if (cnt[root] == 1) {
            let rootSize = city.size[root];
            if (rootSize > ansSize || (rootSize == ansSize && node < ans)) {
                ansSize = rootSize;
                ans = node;
            }
        }
    }

    if (ans == -1) {
        ans = Infinity;
        for (let node of initial)
            ans = Math.min(ans, node);
    }
    return ans;
};

复杂度

时间复杂度：O(n^2)
空间复杂度：O(n)

[yan0327]

type UnionFindSet struct{
    Parents []int
    Size []int
}
func (u *UnionFindSet) Init(size int){
    u.Parents = make([]int,size)
    u.Size = make([]int,size)
    for i:=0;i<size;i++{
        u.Parents[i] = i
        u.Size[i] = 1
    }
}
func (u *UnionFindSet) Find(node int)int{
    if u.Parents[node] == node{
        return node
    }
    root := u.Find(u.Parents[node])
    u.Parents[node] = root
    return root
}
func (u *UnionFindSet) Union(node1 int,node2 int){
    root1 := u.Find(node1)
    root2 := u.Find(node2)
    if root1 == root2{
        return
    }
    if root1 < root2{
        u.Parents[root1] = root2
        u.Size[root2] += u.Size[root1]
    }
}
func minMalwareSpread(graph [][]int, initial []int) int {
    u := &UnionFindSet{}
    u.Init(len(graph))
    for i:=0;i<len(graph);i++{
        for j:=0;j<len(graph[i]);j++{
            if graph[i][j] == 1{
                u.Union(i,j)
            }
        }
    }
    sort.Ints(initial)
    count := make(map[int]int,0)
    for i:=0;i<len(initial);i++{
        count[u.Find(initial[i])]++
    }
    out := -1
    outSize := -1
    root := 0
    for i:=0;i<len(initial);i++{
        root = u.Find(initial[i])
        if count[root]==1 && (out == -1 || outSize < u.Size[root]){
            out = initial[i]
            outSize = u.Size[root]
        }
    }
    if out == -1{
        out = initial[0]
    }
    return out
}

[Tesla-1i]

class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        def dfs(i):
            nodes.add(i)
            for j in range(len(graph[i])):
                if graph[i][j] and j not in nodes:
                    dfs(j)
        rank, initial = collections.defaultdict(list), set(initial)
        for node in sorted(initial):
            nodes = set()
            dfs(node)
            if nodes & initial == {node}:
                rank[len(nodes)].append(node)
        return rank[max(rank)][0] if rank else min(initial)

[ZacheryCao]

Code

class DSU:
    def __init__(self, N):
        self.p = [i for i in range(N)]
        self.sz = [1] * N

    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]

    def union(self, x, y):
        xr = self.find(x)
        yr = self.find(y)
        self.p[xr] = yr
        self.sz[yr] += self.sz[xr]

    def size(self, x):
        return self.sz[self.find(x)]

class Solution(object):
    def minMalwareSpread(self, graph, initial):
        dsu = DSU(len(graph))

        for j, row in enumerate(graph):
            for i in range(j):
                if row[i]:
                    dsu.union(i, j)

        count = collections.Counter(dsu.find(u) for u in initial)
        ans = (-1, min(initial))
        for node in initial:
            root = dsu.find(node)
            if count[root] == 1:  # unique color
                if dsu.size(root) > ans[0]:
                    ans = dsu.size(root), node
                elif dsu.size(root) == ans[0] and node < ans[1]:
                    ans = dsu.size(root), node

        return ans[1]

[ZJP1483469269]

class Solution:
    def minMalwareSpread(self, g: List[List[int]], initial: List[int]) -> int:
        n = len(g)
        p = [i for i in range(n)]
        s = [1] * n
        def find(x):
            if p[x] != x:
                p[x] = find(p[x])
            return p[x]

        for i in range(n):
            for j in range(i+1,n):
                if g[i][j]:
                    a , b = find(i) , find(j)
                    if not a == b:
                        p[a] = b
                        s[b] += s[a]
        ans = -1
        initial.sort()
        cnt = Counter([find(i) for i in initial])
        for x in initial:
            if ans != -1:
                cc = 0 if cnt[find(ans)] > 1 else s[find(ans)]
            if ans == -1 or (s[find(x)] > cc and cnt[find(x)] == 1):
                ans = x
        return ans

[charlestang]

思路

使用并查集，用代表元法。统计每个代表元链接的节点数，用哈希存好。

然后，对每个 initial 节点，统计去掉这个节点后，感染的总数，取最小值时候的 initial值。

代码

class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        n = len(graph)
        p = [i for i in range(n)]

        def find(x:int) -> int:
            if p[x] == x:
                return x
            return find(p[x])

        def union(x: int, y: int):
            px = find(x)
            py = find(y)
            if px != py:
                p[px] = py

        for i in range(n):
            for j in range(i + 1, n):
                if graph[i][j] == 1:
                    union(i, j)

        cnt = defaultdict(int)
        for i in range(n):
            cnt[find(i)] += 1

        initial.sort()
        M = n
        I = initial[0]
        for j in initial:
            infected = set()
            total = 0
            for i in initial:
                if i == j: continue
                pi = find(i)
                if pi not in infected:
                    infected.add(pi)
                    total += cnt[pi]
            if total < M:
                M = total
                I = j
        return I

[xinhaoyi]

class Solution { public int minMalwareSpread(int[][] graph, int[] initial) { UnionFind un = new UnionFind(graph.length); for (int y = 0; y < graph.length; y++) { for (int x = 0; x < graph[0].length; x++) { if (graph[y][x] == 1) { un.unite(y, x); } } }

    // initial中的参数【属于同一个集合的点】，在initial中有几个：连通分量
    int[] count = new int[graph.length];
    for (int i : initial) {
        count[un.findset(i)]++;
    }

    Arrays.sort(initial);
    int maxCnt = -1;
    int ans = initial[0];
    for (int i = initial.length - 1; i >= 0; i--) {
        int root = un.findset(initial[i]);
        int cnt = un.count(root);
        if (count[root] == 1 && cnt >= maxCnt) {
            // 等于1才有比较的意义
            maxCnt = cnt;
            ans = initial[i];
        }
    }
    return ans;
}

// 并查集模板
class UnionFind {

    // 集合内的元素列表
    int[] parent;

    // 节点深度:一个集合内元素的个数
    int[] size;

    int n;

    // 当前连通分量数目:并查集中的集合数量
    int setCount;

    // key：集合元素索引，value：集合中元素的数量
    Map<Integer, Integer> cntMap = new HashMap<>();

    public UnionFind(int n) {
        this.n = n;
        this.setCount = n;
        this.parent = new int[n];
        this.size = new int[n];
        Arrays.fill(size, 1);
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }

    public int findset(int x) {
        return parent[x] == x ? x : (parent[x] = findset(parent[x]));
    }

    public boolean unite(int x, int y) {
        x = findset(x);
        y = findset(y);
        if (x == y) {
            return false;
        }
        if (size[x] < size[y]) {
            int temp = x;
            x = y;
            y = temp;
        }
        parent[y] = x;
        size[x] += size[y];
        --setCount;
        cntMap.put(x, size[x]);
        return true;
    }

    public boolean connected(int x, int y) {
        x = findset(x);
        y = findset(y);
        return x == y;
    }

    public int count(int root) {
        return cntMap.getOrDefault(root, 1);
    }
}

}

[xuhzyy]

'''
[1,0,0,0,1,0,0,0,0,0,1],
[0,1,0,1,0,0,0,0,0,0,0],
[0,0,1,0,0,0,0,1,0,0,0],
[0,1,0,1,0,1,0,0,0,0,0],
[1,0,0,0,1,0,0,0,0,0,0],
[0,0,0,1,0,1,0,0,1,1,0],
[0,0,0,0,0,0,1,1,0,0,0],
[0,0,1,0,0,0,1,1,0,0,0],
[0,0,0,0,0,1,0,0,1,0,0],
[0,0,0,0,0,1,0,0,0,1,0],
[1,0,0,0,0,0,0,0,0,0,1]
'''

class UnionFind:
    def __init__(self, n):
        self.father = {}
        self.size = {}
        for i in range(n):
            self.father[i] = i
            self.size[i] = 1

    def find(self, x):
        root = x
        while(self.father[root] != root):
            root = self.father[root]
        while(self.father[x] != root):
            ori_father = self.father[x]
            self.father[x] = root
            self.size[x] = 1
            x = ori_father
        return root

    def union(self, x, y):
        father_x, father_y = self.find(x), self.find(y)
        if father_x != father_y:
            self.father[father_x] = father_y
            self.size[father_y] += self.size[father_x]

    def isConnected(self, x, y):
        return self.find(x) == self.find(y)

class Solution(object):
    def minMalwareSpread(self, graph, initial):
        """
        :type graph: List[List[int]]
        :type initial: List[int]
        :rtype: int
        """
        n = len(graph)
        uf = UnionFind(n)
        for i in range(n-1):
            for j in range(i+1, n):
                if graph[i][j] == 1:
                    uf.union(i, j)

        initial.sort()
        freq = collections.defaultdict(int)
        for x in initial:
            father_x = uf.find(x)
            freq[father_x] += 1

        index, maxsize = 0, 0
        for i in range(len(initial)):
            x = initial[i]
            father_x = uf.find(x)
            if freq[father_x] == 1:
                size = uf.size[father_x]
                if size > maxsize:
                    index = i
                    maxsize = size

        return initial[index]

[zol013]

class UnionFind:
    def __init__(self):
        self.father = {}
        self.size = {}

    def find(self, x):
        self.father.setdefault(x, x)
        if x != self.father[x]:
            self.father[x] = self.find(self.father[x])
        return self.father[x]

    def union(self, x, y):
        fx, fy = self.find(x), self.find(y)
        if self.size.setdefault(fx, 1) < self.size.setdefault(fy, 1):
            self.father[fx] = fy
            self.size[fy] += self.size[fx]
        elif fx != fy:
            self.father[fy] = fx
            self.size[fx] += self.size[fy]

class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        uf = UnionFind()

        for i in range(len(graph)):
            for j in range(i, len(graph)):
                if graph[i][j]:
                    uf.union(i, j)

        initial.sort()
        max_size, index, fi = 0, -1, []
        cnt = collections.defaultdict(int)
        for init in initial:
            fi.append(uf.find(init))
            cnt[fi[-1]] += 1
        for i in range(len(initial)):
            if cnt[fi[i]] > 1:
                continue
            if uf.size[fi[i]] > max_size:
                max_size = uf.size[fi[i]]
                index = initial[i]

        return index if index != -1 else initial[0]

[zhiyuanpeng]

class DSU:
    def __init__(self, N):
        self.p = range(N)
        self.sz = [1] * N

    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]

    def union(self, x, y):
        xr = self.find(x)
        yr = self.find(y)
        self.p[xr] = yr
        self.sz[yr] += self.sz[xr]

    def size(self, x):
        return self.sz[self.find(x)]

class Solution(object):
    def minMalwareSpread(self, graph, initial):
        dsu = DSU(len(graph))

        for j, row in enumerate(graph):
            for i in xrange(j):
                if row[i]:
                    dsu.union(i, j)

        count = collections.Counter(dsu.find(u) for u in initial)
        ans = (-1, min(initial))
        for node in initial:
            root = dsu.find(node)
            if count[root] == 1:  # unique color
                if dsu.size(root) > ans[0]:
                    ans = dsu.size(root), node
                elif dsu.size(root) == ans[0] and node < ans[1]:
                    ans = dsu.size(root), node

        return ans[1]

[tongxw]

思路

1. 求连通分量，并统计连通分量中顶点的数量
2. 把initial中顶点按照连通分量分组。
3. 如果initial中的顶点不和其他initial顶点连通，它可能是答案，取所属连通分量中顶点数量最大的；数量相同时，取顶点数字最小的。

4. 如果按照3的逻辑找不到，排序输出最小顶点。

   
   class Solution {
   public int minMalwareSpread(int[][] graph, int[] initial) {
     int n = graph.length;
     UnionFind uf = new UnionFind(n);
     for (int i=0; i<n; i++) {
       for (int j=0; j<i; j++) {
         if (graph[i][j] == 1) {
           uf.union(i, j);
         }
       }
     }
   
     // group infected nodes by their roots
     Map<Integer, List<Integer>> group = new HashMap<>(); // root -> [infected]
     for (int infected : initial) {
       group.computeIfAbsent(uf.find(infected),  k -> new ArrayList<>()).add(infected);
     }
   
     int ans = n;
     int maxCount = 0;
     for (List<Integer> infectedNodes : group.values()) {
       if (infectedNodes.size() == 1) {
         // this infected node is connected to other infected nodes
         int node = infectedNodes.get(0);
         int count = uf.getSize(node);
         if (count > maxCount) {
           maxCount = count;
           ans = node;
         } else if (count == maxCount && node < ans)  {
           ans = node;
         }
       }
     }
   
     if (ans != n) {
       return ans;
     }
   
     Arrays.sort(initial);
     return initial[0];
   }
   }

class UnionFind { int[] parents; int[] size;

public UnionFind(int n) { parents = new int[n]; size = new int[n]; for (int i=0; i<n; i++) { parents[i] = i; size[i] = 1; } }

public int find(int x) { while (x != parents[x]) { x = parents[x]; }

return x;

}

public void union(int x, int y) { int px = find(x); int py = find(y); if (px != py) { // x -> y parents[px] = py; size[py] += size[px]; } }

public int getSize(int x) { return size[find(x)]; } }

TC: O(N^2)
SC: O(N)

[honeymeng-hub]

class Solution {

public int minMalwareSpread(int[][] graph, int[] initial) {
    int n = graph.length;
    UF uf = new UF(n);
    for(int i=0;i<n;i++) {
        for(int j=i+1;j<n;j++) {
            if(graph[i][j]==1) {
                uf.union(i,j);
            }
        }
    }
    int[] count = new int[n];
    for(int node: initial) {
        count[uf.find(node)]++;
    }
    int ans=-1, ansSize=-1;
    for(int node: initial) {
        int root = uf.find(node);
        if(count[root]==1) {
            int currSize = uf.getSize(root);
            if(currSize>ansSize) {
                ansSize=currSize;
                ans=node;
            }
            else if(currSize == ansSize && node < ans) {
                ans=node;
            }
        }
    }
    if(ans==-1) {
        ans=n+1;
        for(int node: initial) {
            ans = Math.min(node,ans);
        }
    }
    return ans;

}
class UF {
    int[] parent;
    int[] size;

    public UF(int n) {
        parent = new int[n];
        size = new int[n];
        for(int i=0;i<n;i++) {
            parent[i]=i;
            size[i]=1;
        }
    }
    public int find(int x) {
        while(parent[x]!=x) {
            parent[x]=parent[parent[x]];
            x=parent[x];
        }
        return parent[x];
    }
    public int getSize(int x) {
        return size[find(x)];
    }
    public void union(int x, int y) {
        int xroot = find(x);
        int yroot = find(y);
        if(xroot!=yroot) {
            if(size[xroot]>size[yroot]) {
                parent[yroot]=xroot;
                size[xroot]+=size[yroot];
            }
            else {
                parent[xroot]=yroot;
                size[yroot]+=size[xroot];
            }
        }

    }

}

}

[LannyX]

思路

DFS

代码

class Solution:
    def minMalwareSpread(self, graph, initial):
        def dfs(i):
            nodes.add(i)
            for j in range(len(graph[i])):
                if graph[i][j] and j not in nodes:
                    dfs(j)
        rank, initial = collections.defaultdict(list), set(initial)
        for node in sorted(initial):
            nodes = set()
            dfs(node)
            if nodes & initial == {node}:
                rank[len(nodes)].append(node)
        return rank[max(rank)][0] if rank else min(initial)

[liuzekuan]

思路

并查集之后统计每个集合的点数，以及每个集合有多少个感染的结点，不去掉initial中的点时统计没有被感染的总数num，对initial进行排序，遍历initial的p点，然后看p所在集合的点数n和感染数inf（感染数》=1），inf>1 那么去掉p的未感染总数all = num + n,否则为num，遍历完成的p即为答案

代码

• 语言支持：Java

Java Code:

class Solution {
    public int minMalwareSpread(int[][] graph, int[] initial) {
        UnionFind unionFind = new UnionFind(graph.length);
        for (int i = 0; i < graph.length; i++) {
            for (int j = i+1; j < graph.length; j++) {
                if (graph[i][j] == 0)continue;
                unionFind.unionVertical(i,j);
            }
        }
        boolean[] isInfected = new boolean[graph.length];
        for (int i = 0; i < initial.length; i++) {
            isInfected[initial[i]] = true;
        }
        HashMap<Integer,List<Integer>> map = new HashMap();
        for (int i = 0; i < graph.length; i++) {
            int root = unionFind.getRoot(i);
            if (!map.containsKey(root)){
                map.put(root,new LinkedList<>());
            }
            map.get(root).add(i);
        }
        int num = 0;
        for (Integer key :map.keySet()){
            List<Integer> set = map.get(key);
            int infCount = 0;
            for (Integer p:set){
                if (isInfected[p])infCount++;
            }
            if (infCount==0){
                num += set.size();
            }
            map.get(key).add(infCount);
        }
        int all = 0,fec = 0;
        int maxRemain = -1,n,ip = -1; 
        Arrays.sort(initial);
        for (int i = 0; i < initial.length; i++) {
            List<Integer> set = map.get(unionFind.getRoot(initial[i]));
            all = set.size()-1;
            fec = set.get(set.size()-1);
            if (fec == 1){
                n = num+all;
            }else {
                n = num;
            }
            if (maxRemain < n){
                maxRemain = n;
                ip = initial[i];
            }
        }
        return ip;
    }
    class UnionFind{
        int parent[];
        int setCount;
        int rank[];
        public UnionFind(int n) {
            parent = new int[n];
            rank = new int[n];
            setCount = n;
            for (int i = 0; i < n; i++) {
                parent[i] = -1;
            }
        }

        public int getRoot(int x){
            int root = x;
            while (parent[root] != -1){
                root = parent[root];
            }
            return root;
        }
        public boolean unionVertical(int x,int y){
            int rootX = getRoot(x);
            int rootY = getRoot(y);
            if (rootX == rootY) return false;
            if (rank[rootX] > rank[rootY]){
                parent[rootY] = rootX;
            }else if (rank[rootX] < rank[rootY]){
                parent[rootX] = rootY;
            }else {
                parent[rootX] = rootY;
                rank[rootY]++;
            }
            setCount--;
            return true;
        }
    }
}

[falconruo]

思路:

并查集

复杂度分析:

• 时间复杂度: O(N * N)
• 空间复杂度: O(N)

代码(C++):

class UF {
public:
    vector<int> parent;
    vector<int> size;
    vector<int> infected;
    UF(int n) {
        size = vector<int>(n, 1);
        parent.resize(n);
        for (int i = 0; i < n; i++)
            parent[i] = i;
        infected.resize(n);
    }

    int Find(int x) {
        if (x != parent[x])
            parent[x] = Find(parent[x]);

        return parent[x];
    }

    void Union(int x, int y) {
        int px = Find(x);
        int py = Find(y);
        if (py != px) {
            parent[px] = py;
            size[py] += size[px];
        }
    }
};

class Solution {
public:
    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
        int n = graph.size();

        UF uf(n * n);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (graph[i][j])
                    uf.Union(i, j);
            }
        }

        sort(initial.begin(), initial.end());
        for (auto node : initial) {
            int p = uf.Find(node);
            uf.infected[p]++;
        }

        int num = 0, res = -1;
        for (auto node : initial) {
            int p = uf.Find(node);
            if (uf.infected[p] == 1) {
                if (num < uf.size[p]) {
                    num = uf.size[p];
                    res = node;
                }
            }
        }

        return res == -1 ? initial[0] : res;
    }
};

[luhnn120]

思路

并查集

代码

class UnionFind {
    constructor(size) {
        this.parents = Array(size)
            .fill(0)
            .map((_, i) => i);
        this.sizes = Array(size).fill(1);
    }
    find(x) {
        if (x !== this.parents[x]) {
            this.parents[x] = this.find(this.parents[x]);
        }
        return this.parents[x];
    }
    getSize(x) {
        return this.sizes[this.find(x)];
    }

    union(a, b) {
        const fa = this.find(a);
        const fb = this.find(b);
        if (fa == fb) {
            return;
        }

        if (this.sizes[fa] < this.sizes[fb]) {
            this.parents[fa] = fb;
            // fb是root
            this.sizes[fb] += this.sizes[fa];
        } else {
            this.parents[fb] = fa;
            // fa是root
            this.sizes[fa] += this.sizes[fb];
        }

    }
}

/**
 * 
 * @param {*} graph 
 * @param {*} initial 
 */
var minMalwareSpread = function (graph, initial) {
    const uf = new UnionFind(graph.length);
    for (let i = 0; i < graph.length; i++) {
        for (let j = 0; j < graph.length; j++) {
            graph[i][j] === 1 && uf.union(i, j);
        }
    }

    let minNumbers = Infinity, minIndex = initial[0];
    for (let i = 0; i < initial.length; i++) {
        let temNumbers = getInfectedNumbers([
            ...initial.slice(0, i),
            ...initial.slice(i + 1)
        ]);

        if (minNumbers > temNumbers) {
            minIndex = initial[i];
            minNumbers = temNumbers;
        } else if (minNumbers === temNumbers && minIndex > initial[i]) {
            minIndex = initial[i];
        }
    }
    return minIndex;

    function getInfectedNumbers(initial) {
        const roots = [];
        for (let i = 0; i < initial.length; i++) {
            const p = uf.find(initial[i]);
            roots.includes(p) || roots.push(p);
        }

        return roots.reduce((prev, curr) => prev + uf.getSize(curr), 0);
    }
};

复杂度

时间复杂度：O(n^2) 空间复杂度：O(n)

[declan92]

思路

1. 使用并查集统计每个连通分量的结点数size;
2. 统计出每个连通分量包含initial结点的数量count;
3. 如果count等于1,返回size最大的连通分量包含的initial结点,多个结点则返回最小值;
4. 如果count都不等于1,initial最小结点

步骤

1. 并查集api:init(int n),int find(int x),union(int x,int y),int getSize(int x);
2. 初始化并查集,求出并查集每个连通分量的结点数size;
3. 求出并查集每个连通分量包含的initial结点数count;
4. count=1的连通分量,返回size最大所包含的initial结点,如果size最大有多个值,返回initial结点最小的值;
5. count没有等于1的连通分量,返回initial结点最小的值;

java

class Solution {
    public int minMalwareSpread(int[][] graph, int[] initial) {
        int n = graph.length;
        UF uf = new UF(n);
        int[] count = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (graph[i][j] == 1) {
                    uf.union(i, j);
                }
            }
        }
        for (int node : initial) {
            count[uf.find(node)]++;
        }
        int ansSize = -1, ansNode = -1;
        for (int node : initial) {
            int rootNode = uf.find(node);
            if(count[rootNode]==1){
                int curSize = uf.getSize(rootNode);
                if(curSize>ansSize){
                    ansSize = curSize;
                    ansNode = node;
                }else if(curSize==ansSize&&ansNode>node){
                    ansNode = node;
                }
            }
        }
        if(ansNode==-1){
            ansNode = n+1;
            for(int node:initial){
                ansNode = Math.min(ansNode, node);
            }
        }
        return ansNode;
    }
}

class UF {
    int[] parent;
    int[] size;

    public UF(int n){
        parent = new int[n];
        size = new int[n];
        for(int i = 0; i < n; i++){
            parent[i] = i;
            size[i] = 1;
        }
    }

    public int getSize(int x) {
        return size[find(x)];
    }

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

    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY)
            return;
        if (size[rootX] <= size[rootY]) {
            parent[rootX] = rootY;
            size[rootY] += size[rootX];
        } else {
            parent[rootY] = rootX;
            size[rootX] += size[rootY];
        }
    }

}

时间:$O(n^2)$
空间:$O(n)$

[yinhaoti]

class UF:
    def __init__(self, M):
        self.parent = {}
        self.size = {}
        self.cnt = 0
        for i in range(len(M)):
            self.parent[i] = i
            self.cnt += 1
            self.size[i] = 1

    def find(self, x):
        if x != self.parent[x]:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
        return x

    def union(self, p, q):
        if self.connected(p, q): return
        leader_p = self.find(p)
        leader_q = self.find(q)
        if self.size[leader_p] < self.size[leader_q]:
            self.parent[leader_p] = leader_q
            self.size[leader_q] += self.size[leader_p]
        else:
            self.parent[leader_q] = leader_p
            self.size[leader_p] += self.size[leader_q]
        self.cnt -= 1

    def connected(self, p, q):
        return self.find(p) == self.find(q)

class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        """
        Keywords: graph
        Topic: Union-find

        """
        uf = UF(graph)

        for i in range(len(graph)):
            for j in range(i, len(graph)):
                if graph[i][j]:
                    uf.union(i, j)
        initial.sort()
        print(uf.parent)

        max_size, index, fi = 0, -1, []
        cnt = collections.defaultdict(int)
        for init in initial:
            fi.append(uf.find(init))
            cnt[fi[-1]] += 1
        print(fi, cnt)

        for i in range(len(initial)):
            print(cnt[fi[i]])
            if cnt[fi[i]] > 1:
                continue
            if uf.size[fi[i]] > max_size:
                max_size = uf.size[fi[i]]
                index = initial[i]
        return index if index != -1 else initial[0]

[1149004121]

924. 尽量减少恶意软件的传播

思路

并查集。如果initial中的结点相连，则删去其中任意一个还是会扩散，如果initial中的结点不与initial中的其他结点相连，则删去他，则不会扩散。

代码

var minMalwareSpread = function (graph, initial) {
  let dfu = new DFU(graph.length);
  for (let i = 0; i < graph.length; i++) {
    for (let j = i + 1; j < graph.length; j++) {
      if (graph[i][j]) dfu.union(i, j);
    }
  };
  let counts = initial.map(node => dfu.find(node)).reduce((obj, root) => {
    if (!obj[root]) obj[root] = 0;
    obj[root]++;
    return obj;
  }, {})
  let res = Math.min(...initial), count = 0;
  for (let init of initial) {
    let root = dfu.find(init);
    if (counts[root] === 1) {
      if ((dfu.counts[root] > count) || ((dfu.counts[root] === count) && res > init)) {
        res = init;
        count = dfu.counts[root];
      }
    }
  }

  return res
};

class DFU {
  constructor(n) {
    this.parent = new Array(n).fill(0).map((item, index) => index);
    this.counts = new Array(n).fill(1);
  };
  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]);
    };
    return this.parent[x];
  };
  union(x, y) {
    if (this.isConnect(x, y)) return;
    let rootX = this.find(x);
    let rootY = this.find(y);
    if (this.counts[rootX] < this.counts[rootY]) {
      this.parent[rootX] = rootY;
      this.counts[rootY] += this.counts[rootX];
    } else {
      this.parent[rootY] = rootX;
      this.counts[rootX] += this.counts[rootY];
    }
  };
  isConnect(x, y) {
    return this.find(x) === this.find(y);
  }
}

复杂度分析

• 时间复杂度：O(N^2) 。
• 空间复杂度：O(N) 。

[Aobasyp]

var minMalwareSpread = function (graph, initial) { const N = graph.length; initial.sort((a, b) => a - b); let colors = Array.from({ length: N }).fill(0); let curColor = 1; // 给联通分量标色 for (let i = 0; i < N; i++) { if (colors[i] === 0) { dfs(i, curColor++); } }

let counts = Array.from({ length: curColor }).fill(0); for (node of initial) { counts[colors[node]]++; }

let maybe = []; for (node of initial) { if (counts[colors[node]] === 1) { maybe.push(node); } }

counts.fill(0);

for (let i = 0; i < N; i++) { counts[colors[i]]++; }

let res = -1; let maxCount = -1;

for (let node of maybe) { if (counts[colors[node]] > maxCount) { maxCount = counts[colors[node]]; res = node; } }

if (res === -1) { res = Math.min(...initial); }

return res;

function dfs(start, color) { colors[start] = color; for (let i = 0; i < N; i++) { if (graph[start][i] === 1 && colors[i] === 0) { dfs(i, color); } } } };

时间复杂度： O(d^2) 空间复杂度： O(d)

[hdyhdy]

const MaxInt = int(^uint(0) >> 1)

func minMalwareSpread(graph [][]int, initial []int) int {
    colors := make([]int, len(graph))
    for i := 0; i < len(graph); i++ {
        colors[i] = -1
    }

    c := 0
    for node := 0; node < len(graph); node++ {
        if colors[node] == -1 {
            dfs(graph, colors, node, c)
            c++
        }
    }

    size := make([]int, c)
    for _, color := range colors {
        size[color]++
    }

    colorCnt := make([]int, c)
    for _, node := range initial {
        colorCnt[colors[node]]++
    }

    ans := MaxInt
    for _, node := range initial {
        color := colors[node]
        if colorCnt[color] == 1 {
            if ans == MaxInt {
                ans = node
            } else if size[color] > size[colors[ans]] {
                ans = node
            } else if size[color] == size[colors[ans]] && node < ans {
                ans = node
            }
        }
    }
    if ans == MaxInt {
        for _, node := range initial {
            ans = min(ans, node)
        }
    }
    return ans
}

func dfs(graph [][]int, colors []int, node, color int) {
    colors[node] = color
    for nei := 0; nei < len(graph); nei++ {
        if graph[node][nei] == 1 && colors[nei] == -1 {
            dfs(graph, colors, nei, color)
        }
    }
}

func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

[guangsizhongbin]

type UnionFindSet struct { Parents []int //记录每个节点的上级 Size []int // 记录以当前结点为顶点的连通分量里面的节点有多少个（只有自己的话，值为1） }

func (u *UnionFindSet) Init(size int) { u.Parents = make([]int, size) u.Size = make([]int, size) for i := 0; i < size; i++ { u.Parents[i] = i u.Size[i] = 1 } }

func (u *UnionFindSet) Find(node int) int { if u.Parents[node] == node { return node } root := u.Find(u.Parents[node]) u.Parents[node] = root return root }

func (u *UnionFindSet) Union(node1 int, node2 int) { root1 := u.Find(node1) root2 := u.Find(node2) if root1 == root2 { return } if root1 < root2 { u.Parents[root1] = root2 u.Size[root2] += u.Size[root1] // 以root2为最顶层结点的连通分量的个数要叠加上root1的 } }

func minMalwareSpread(graph [][]int, initial []int) int { // 初始化并查集 u := &UnionFindSet{} u.Init(len(graph))

// 根据graph进行连通，生成连通分量，并记录连通分量的大小
for i := 0; i < len(graph); i++ {
    for j := 0; j < len(graph[i]); j++ {
        if graph[i][j] == 1 {
            u.Union(i,j)
        }
    }
}

// 查找目标，统计每个感染节点的颜色情况
// 先对Init进行排序 
sort.Ints(initial)
count := make(map[int]int,0)
for i := 0; i < len(initial); i++ {
    count[u.Find(initial[i])]++
}
// 1. 如果有唯一颜色的，就选择其中连通分量最大的
ans := -1
ansSize := -1
root := 0
for i := 0; i < len(initial); i++ {
    // 是唯一颜色的
    root = u.Find(initial[i])
    if count[root] == 1 && (ans == -1 || ansSize < u.Size[root]) {
        ans = initial[i]
        ansSize = u.Size[root]
    }
}

// 2. 如果没有唯一颜色的节点，就选择下标最小的
if ans == -1 {
    ans = initial[0]
}
return ans

}

[CodingProgrammer]

思路

并查集

代码

class Solution {
    private static class UnionSet {
        int[] array;
        int[] weights;
        UnionSet(int size) {
            array = new int[size];
            weights = new int[size];
            for (int i = 0; i < array.length; i++) {
                array[i] = -1;
                weights[i] = 1;
            }
        }
        int find(int x) {
            while (array[x] >= 0) {
                x = array[x];
            }
            return x;
        }
        void union(int x, int y) {
            if (x == y)
                return;
            if (weights[x] > weights[y]) {
                int temp = x;
                x = y;
                y = temp;
            }
            weights[y] += weights[x];
            array[x] = y;
        }
        int getWeight(int x) {
            return weights[x];
        }
    }

    public int minMalwareSpread(int[][] graph, int[] initial) {
        Arrays.sort(initial);
        UnionSet us = new UnionSet(graph.length);
        for (int i = 0; i < graph.length; i++)
            for (int j = i + 1; j < graph[0].length; j++)
                if (graph[i][j] != 0) {
                    int rootX = us.find(i), rootY = us.find(j);
                    us.union(rootX, rootY);
                }
        Map<Integer, Integer> map = new HashMap<>();
        for (int index: initial) {
            int root = us.find(index);
            if (map.containsKey(root))
                map.put(root, -1);
            else {
                map.put(root, index);
            }
        }
        int max = -1, result = initial[0];
        for (Map.Entry<Integer, Integer> entry: map.entrySet()) {
            int root = entry.getKey();
            int index = entry.getValue();
            if (index == -1)
                continue;
            int count = us.getWeight(root);
            if (count > max || (count == max && index < result)) {
                max = count;
                result = index;
            }
        }
        return result;
    }

}

复杂度

• 时间复杂度：O(N^2)
• 空间复杂度：O(N)

[shamworld]

var minMalwareSpread = function (graph, initial) {
  const N = graph.length;
  initial.sort((a, b) => a - b);
  let colors = Array.from({ length: N }).fill(0);
  let curColor = 1;
  // 给联通分量标色
  for (let i = 0; i < N; i++) {
    if (colors[i] === 0) {
      dfs(i, curColor++);
    }
  }

  let counts = Array.from({ length: curColor }).fill(0);
  for (node of initial) {
    counts[colors[node]]++;
  }

  let maybe = [];
  for (node of initial) {
    if (counts[colors[node]] === 1) {
      maybe.push(node);
    }
  }

  counts.fill(0);

  for (let i = 0; i < N; i++) {
    counts[colors[i]]++;
  }

  let res = -1;
  let maxCount = -1;

  for (let node of maybe) {
    if (counts[colors[node]] > maxCount) {
      maxCount = counts[colors[node]];
      res = node;
    }
  }

  if (res === -1) {
    res = Math.min(...initial);
  }

  return res;

  function dfs(start, color) {
    colors[start] = color;
    for (let i = 0; i < N; i++) {
      if (graph[start][i] === 1 && colors[i] === 0) {
        dfs(i, color);
      }
    }
  }
};

[WANGDI-1291]

代码

class UnionFind:
    def __init__(self):
        self.father = {}
        self.size = {}

    def find(self, x):
        self.father.setdefault(x, x)
        if x != self.father[x]:
            self.father[x] = self.find(self.father[x])
        return self.father[x]

    def union(self, x, y):
        fx, fy = self.find(x), self.find(y)
        if self.size.setdefault(fx, 1) < self.size.setdefault(fy, 1):
            self.father[fx] = fy
            self.size[fy] += self.size[fx]
        elif fx != fy:
            self.father[fy] = fx
            self.size[fx] += self.size[fy]

class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        uf = UnionFind()

        for i in range(len(graph)):
            for j in range(i, len(graph)):
                if graph[i][j]:
                    uf.union(i, j)

        initial.sort()
        max_size, index, fi = 0, -1, []
        cnt = collections.defaultdict(int)
        for init in initial:
            fi.append(uf.find(init))
            cnt[fi[-1]] += 1
        for i in range(len(initial)):
            if cnt[fi[i]] > 1:
                continue
            if uf.size[fi[i]] > max_size:
                max_size = uf.size[fi[i]]
                index = initial[i]

        return index if index != -1 else initial[0]

[Riuusee]

思路

官方题解——并查集

代码

class Solution {
    public int minMalwareSpread(int[][] graph, int[] initial) {
        int n = graph.length;
        UF uf = new UF(n);
        for(int i=0;i<n;i++) {
            for(int j=i+1;j<n;j++) {
                if(graph[i][j]==1) {
                    uf.union(i,j);
                }
            }
        }
        int[] count = new int[n];
        for(int node: initial) {
            count[uf.find(node)]++;
        }
        int ans=-1, ansSize=-1;
        for(int node: initial) {
            int root = uf.find(node);
            if(count[root]==1) {
                int currSize = uf.getSize(root);
                if(currSize>ansSize) {
                    ansSize=currSize;
                    ans=node;
                }
                else if(currSize == ansSize && node < ans) {
                    ans=node;
                }
            }
        }
        if(ans==-1) {
            ans=n+1;
            for(int node: initial) {
                ans = Math.min(node,ans);
            }
        }
        return ans;

    }
    class UF {
        int[] parent;
        int[] size;

        public UF(int n) {
            parent = new int[n];
            size = new int[n];
            for(int i=0;i<n;i++) {
                parent[i]=i;
                size[i]=1;
            }
        }
        public int find(int x) {
            while(parent[x]!=x) {
                parent[x]=parent[parent[x]];
                x=parent[x];
            }
            return parent[x];
        }
        public int getSize(int x) {
            return size[find(x)];
        }
        public void union(int x, int y) {
            int xroot = find(x);
            int yroot = find(y);
            if(xroot!=yroot) {
                if(size[xroot]>size[yroot]) {
                    parent[yroot]=xroot;
                    size[xroot]+=size[yroot];
                }
                else {
                    parent[xroot]=yroot;
                    size[yroot]+=size[xroot];
                }
            }

        }

    }
}

[Hacker90]

官方题解——并查集

代码 class Solution { public int minMalwareSpread(int[][] graph, int[] initial) { int n = graph.length; UF uf = new UF(n); for(int i=0;i<n;i++) { for(int j=i+1;j<n;j++) { if(graph[i][j]==1) { uf.union(i,j); } } } int[] count = new int[n]; for(int node: initial) { count[uf.find(node)]++; } int ans=-1, ansSize=-1; for(int node: initial) { int root = uf.find(node); if(count[root]==1) { int currSize = uf.getSize(root); if(currSize>ansSize) { ansSize=currSize; ans=node; } else if(currSize == ansSize && node < ans) { ans=node; } } } if(ans==-1) { ans=n+1; for(int node: initial) { ans = Math.min(node,ans); } } return ans;

}
class UF {
    int[] parent;
    int[] size;

    public UF(int n) {
        parent = new int[n];
        size = new int[n];
        for(int i=0;i<n;i++) {
            parent[i]=i;
            size[i]=1;
        }
    }
    public int find(int x) {
        while(parent[x]!=x) {
            parent[x]=parent[parent[x]];
            x=parent[x];
        }
        return parent[x];
    }
    public int getSize(int x) {
        return size[find(x)];
    }
    public void union(int x, int y) {
        int xroot = find(x);
        int yroot = find(y);
        if(xroot!=yroot) {
            if(size[xroot]>size[yroot]) {
                parent[yroot]=xroot;
                size[xroot]+=size[yroot];
            }
            else {
                parent[xroot]=yroot;
                size[yroot]+=size[xroot];
            }
        }

    }

}

}

[machuangmr]

代码

class Solution {
    public int minMalwareSpread(int[][] graph, int[] initial) {
         Arrays.sort(initial);

        int N = graph.length;
        UnionFind uf = new UnionFind(N);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (graph[i][j] == 1) {
                    uf.union(i, j);
                }
            }
        }

        int[] count = new int[N];
        for (int i : initial) {
            count[uf.find(i)]++;
        }

        int maxCCSize = Integer.MIN_VALUE;          // Connected Component 连通分量
        int index = initial[0];
        for (int i : initial) {
            int root = uf.find(i);
            if (count[root] == 1 && uf.size[root] > maxCCSize) {
                maxCCSize = uf.size[root];
                index = i;
            }
        }
        return index;
    }
     class UnionFind {
        int count;      // 连通分量个数
        int[] parent;   // 节点i的父节点是parent[i]
        int[] size;

        public UnionFind(int N) {
            this.count = N;         // n为图的节点总数
            parent = new int[N];
            size = new int[N];
            for (int i = 0; i < N; i++) {
                parent[i] = i;      // 父节点指针初始指向自己
                size[i] = 1;
            }
        }

        public void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX == rootY) {
                return;
            }
            size[rootY] += size[rootX];
            parent[rootX] = rootY;          // x成为y的子树
            count--;
        }

        public int find(int x) {
            if (x != parent[x]) {
                size[find(parent[x])] += size[parent[x]];
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }
    }
}

[fornobugworld]

class Solution(object): def minMalwareSpread(self, graph, initial):

1. Color each component.

    # colors[node] = the color of this node.

    N = len(graph)
    colors = {}
    c = 0

    def dfs(node, color):
        colors[node] = color
        for nei, adj in enumerate(graph[node]):
            if adj and nei not in colors:
                dfs(nei, color)

    for node in xrange(N):
        if node not in colors:
            dfs(node, c)
            c += 1

    # 2. Size of each color.
    # size[color] = number of occurrences of this color.
    size = collections.Counter(colors.values())

    # 3. Find unique colors.
    color_count = collections.Counter()
    for node in initial:
        color_count[colors[node]] += 1

    # 4. Answer
    ans = float('inf')
    for x in initial:
        c = colors[x]
        if color_count[c] == 1:
            if ans == float('inf'):
                ans = x
            elif size[c] > size[colors[ans]]:
                ans = x
            elif size[c] == size[colors[ans]] and x < ans:
                ans = x

    return ans if ans < float('inf') else min(initial)    

[hx-code]

class Solution { public int minMalwareSpread(int[][] graph, int[] initial) { Arrays.sort(initial);

    int N = graph.length;
    UnionFind uf = new UnionFind(N);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (graph[i][j] == 1) {
                uf.union(i, j);
            }
        }
    }

    int[] count = new int[N];
    for (int i : initial) {
        count[uf.find(i)]++;
    }

    int maxCCSize = Integer.MIN_VALUE;          // Connected Component 连通分量
    int index = initial[0];
    for (int i : initial) {
        int root = uf.find(i);
        if (count[root] == 1 && uf.size[root] > maxCCSize) {
            maxCCSize = uf.size[root];
            index = i;
        }
    }
    return index;
}
 class UnionFind {
    int count;      // 连通分量个数
    int[] parent;   // 节点i的父节点是parent[i]
    int[] size;

    public UnionFind(int N) {
        this.count = N;         // n为图的节点总数
        parent = new int[N];
        size = new int[N];
        for (int i = 0; i < N; i++) {
            parent[i] = i;      // 父节点指针初始指向自己
            size[i] = 1;
        }
    }

    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) {
            return;
        }
        size[rootY] += size[rootX];
        parent[rootX] = rootY;          // x成为y的子树
        count--;
    }

    public int find(int x) {
        if (x != parent[x]) {
            size[find(parent[x])] += size[parent[x]];
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
}

}

[pf135145]

代码

var minMalwareSpread = function (graph, initial) {
    const len = graph.length;
    const uf = new UnionFind(len);

    for (let i = 0; i < len; i++) {
        for (let j = 0; j < len; j++) {
            graph[i][j] && uf.unionSet(i, j)
        }
    }

    const getGr = (initarr) => {
        const gr = new Map() // 感染的元
        for (let i of initarr) {
            let item = uf.findSet(i);
            !gr.has(item) && gr.set(item, true)
        }
        return gr
    }

    const js = (map) => {
        let count = 0;
        for (let i = 0; i < len; i++) {
            map.has(uf.findSet(i)) && (count++)
        }
        return count
    }

    let mixall = js(getGr(initial)) // 不删除时候的感染总数
    let res = initial[0] // 初始化删除索引为0的节点
    for (let i = 0; i < initial.length; i++) {
        let tmp = js(getGr([
            ...initial.slice(0, i),
            ...initial.slice(i + 1),
        ]))

        if (tmp < mixall) {
            res = initial[i]
            mixall = tmp
        } else if (tmp === mixall) { 
            initial[i] < res && (res = initial[i])
        }
    }
    return res
};

class UnionFind {
    constructor(size) {
        this.parents = Array(size)
            .fill(0)
            .map((_, i) => i);
        this.sizes = Array(size).fill(1);
    }

    getSizeOfSet(x) {
        const px = this.findSet(x);
        return this.sizes[px];
    }

    findSet(x) {
        if (x !== this.parents[x]) {
            this.parents[x] = this.findSet(this.parents[x]);
        }
        return this.parents[x];
    }

    unionSet(x, y) {
        const px = this.findSet(x);
        const py = this.findSet(y);
        if (px === py) return;
        if (this.sizes[px] > this.sizes[py]) {
            this.parents[py] = px;
            this.sizes[px] += this.sizes[py];
        } else {
            this.parents[px] = py;
            this.sizes[py] += this.sizes[px];
        }
    }
}

[tian-pengfei]

#include <vector>
#include <map>
#include <algorithm>
#include <string>
#include <iostream>
#include <stack>
#include <list>
#include <unordered_map>
#include <sstream>
#include <regex>
#include <set>
#include <math.h>
#include <numeric>
#include <queue>
#include <set>
#include <unordered_set>
using namespace std;

class UnionFind{

    vector<int> parent;

    //初始化自己是自己的父母
public :
    UnionFind(int n){
        parent.resize(n);

        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }

    //把两个集合合起来
    void UnionSet(int i, int j){
        parent[find(i)] = find(j);
    }

    int find(int index){

        if(parent[index]!=index){
            //再寻找过程也可以把自己提到最接近根部的服务是，减少以后查询的时间复杂度
            parent[index] = find(parent[index]);
        }
        return parent[index];
    }

};

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

        int n = graph.size();

        UnionFind uf(n);

        for (int i = 0; i < n; ++i) {
            for (int j = i; j < n; ++j) {
                if(graph[i][j]){
                    uf.UnionSet(i,j);
                }
            }
        }

        unordered_set<int> set;
        for (const auto a:initial){
            set.insert(a);
        }

        unordered_map<int,int> un_set_count;
        unordered_map<int,int> set_count;
        for (int i = 0; i < n; ++i) {
            if(set.find(i)==set.end()){
                un_set_count[uf.find(i)]++;
            }else{
                set_count[uf.find(i)]++;
            }
        }
        int re = -1;
        //得救的人数
        int count = 0;
        sort(initial.begin(),initial.end());
        for (int i = 0; i < initial.size(); ++i) {
            int index = initial[i];
             int root = uf.find(index);
             int _count = 0;
             if(set_count[root]==1){
                 //要理解移除的意思，是把病治好，自己也得救了
                 _count = un_set_count[root]+1;
             }
             if(re==-1||(count<_count)){
                 re = index;
                 count = _count;
             }
             cout<<set_count[root]<<endl;
        }
        return re;
    }
};

[GaoMinghao]

class Solution {

    public int minMalwareSpread(int[][] graph, int[] initial) {
        int n = graph.length;
        UF uf = new UF(n);
        for(int i=0;i<n;i++) {
            for(int j=i+1;j<n;j++) {
                if(graph[i][j]==1) {
                    uf.union(i,j);
                }
            }
        }
        int[] count = new int[n];
        for(int node: initial) {
            count[uf.find(node)]++;
        }
        int ans=-1, ansSize=-1;
        for(int node: initial) {
            int root = uf.find(node);
            if(count[root]==1) {
                int currSize = uf.getSize(root);
                if(currSize>ansSize) {
                    ansSize=currSize;
                    ans=node;
                }
                else if(currSize == ansSize && node < ans) {
                    ans=node;
                }
            }
        }
        if(ans==-1) {
            ans=n+1;
            for(int node: initial) {
                ans = Math.min(node,ans);
            }
        }
        return ans;

    }
    class UF {
        int[] parent;
        int[] size;

        public UF(int n) {
            parent = new int[n];
            size = new int[n];
            for(int i=0;i<n;i++) {
                parent[i]=i;
                size[i]=1;
            }
        }
        public int find(int x) {
            while(parent[x]!=x) {
                parent[x]=parent[parent[x]];
                x=parent[x];
            }
            return parent[x];
        }
        public int getSize(int x) {
            return size[find(x)];
        }
        public void union(int x, int y) {
            int xroot = find(x);
            int yroot = find(y);
            if(xroot!=yroot) {
                if(size[xroot]>size[yroot]) {
                    parent[yroot]=xroot;
                    size[xroot]+=size[yroot];
                }
                else {
                    parent[xroot]=yroot;
                    size[yroot]+=size[xroot];
                }
            }

        }

    }
}

[for123s]

struct node{
    int parent;
    int bad;
    int connect;
    node(int x) : parent(x), bad(0), connect(1) {}
};

class Solution {
public:
    vector<node*> parents;
    int find(int x)
    {
        if(x!=parents[x]->parent)
            return find(parents[x]->parent);
        return x;
    }
    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
        int n = graph.size();
        for(int i=0;i<n;i++)
        {
            parents.push_back(new node(i));
        }
        int m = initial.size();
        int min_idx = n;
        for(int i=0;i<m;i++)
        {
            parents[initial[i]]->bad = 1;
            min_idx = min(min_idx,initial[i]);
        }
        for(int i=0;i<n;i++)
            for(int j=i+1;j<n;j++)
                if(graph[i][j]==1&&find(i)!=find(j))
                {
                    int p_j = find(j);
                    int p_i = find(i);
                    parents[p_i]->parent = p_j;
                    parents[p_j]->connect += parents[p_i]->connect;
                    parents[p_j]->bad += parents[p_i]->bad;
                }
        int max_connect = 0;
        for(int i=0;i<m;i++)
        {
            int p = find(initial[i]);
            if(parents[p]->bad<2)
            {
                if(parents[p]->connect>max_connect)
                {
                    max_connect = parents[p]->connect;
                    min_idx = initial[i];
                }
                else if(parents[p]->connect==max_connect&&min_idx>initial[i])
                    min_idx = initial[i];
            }
        }
        return min_idx;
    }
};

[taojin1992]

class Solution {
// Logic:
/*
1. union find
2. find the largest union with only one initial node infected by malware
    if no such union with only one initial node infected by malware can be found, 
    return the first initial value
*/
    public int minMalwareSpread(int[][] graph, int[] initial) {
        int n = graph.length;
        UF unionFind = new UF(n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (graph[i][j] == 1) {
                    unionFind.union(i, j);
                }
            }
        }
        Arrays.sort(initial);
        // track how many init malware nodes are in each union head
        int[] malCount = new int[n];
        for (int init : initial) {
            malCount[unionFind.find(init)]++;
        }
        // find the unions with only one initial node infected by malware
        // and who is the largest with only one initial
        int maxSize = 0;
        int potential = -1;
        for (int init : initial) {
            int head = unionFind.find(init);
            if (malCount[head] == 1 && unionFind.size[head] > maxSize) {
                maxSize = unionFind.size[head];
                potential = init;
            }
        }        
        return potential == -1 ? initial[0] : potential;
    }

    class UF {
        int size[];
        int parent[];
        int numOfUnions;

        UF(int numOfElements) {
            size = new int[numOfElements];
            parent = new int[numOfElements];
            numOfUnions = numOfElements;
            for (int i = 0; i < numOfElements; i++) {
                size[i] = 1;
                parent[i] = i;
            }
        }

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

        void union(int p, int q) {
            int headOfP = find(p);
            int headOfQ = find(q);
            if (headOfP == headOfQ) {
                return;
            }
            if (size[headOfP] < size[headOfQ]) {
                parent[headOfP] = headOfQ;
                size[headOfQ] += size[headOfP];
            } else {
                parent[headOfQ] = headOfP;
                size[headOfP] += size[headOfQ];
            }
            numOfUnions--;
        }
    }
}

[ZhiweiZhen]

class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        def dfs(i):
            nodes.add(i)
            for j in range(len(graph[i])):
                if graph[i][j] and j not in nodes:
                    dfs(j)
        rank, initial = collections.defaultdict(list), set(initial)
        for node in sorted(initial):
            nodes = set()
            dfs(node)
            if nodes & initial == {node}:
                rank[len(nodes)].append(node)
        return rank[max(rank)][0] if rank else min(initial)

[cszys888]

class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        # step 1 add color
        color = {}
        n = len(graph)
        def dfs(node, c):
            color[node] = c
            for idx, adj in enumerate(graph[node]):
                if adj and idx not in color:
                    dfs(idx, c)
        c = -1
        for i in range(n):
            if i not in color:
                c += 1
                dfs(i, c)

        # step two, count number of colors in color, and number of colors in initial
        from collections import Counter
        from collections import defaultdict
        color_count = Counter(color.values())
        initial_count = defaultdict(int)
        for i in initial:
            c = color[i]
            initial_count[c] += 1

        # select unique from initial_count and return answer
        reduce = 0
        ans = min(initial) # minimum optimal index
        #print(color_count)
        #print(initial_count)
        for i in initial:
            c = color[i]
            if initial_count[c] == 1:
                if color_count[c] > reduce:
                    reduce = color_count[c]
                    ans = i
                elif color_count[c] == reduce:
                    ans = min(ans, i)
                else:
                    continue

        return ans

time complexity: O(n^2) space complexity: O(n)