【Day 77 】2023-01-16 - 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

[whoam-challenge]

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

    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

    size = collections.Counter(colors.values()) 
    color_count = collections.Counter()
    for node in initial:
        color_count[colors[node]] += 1

    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)    

[arinzz]

from collections import defaultdict class Solution: def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:

    n = len(graph)
    edge = defaultdict(dict)
    for i in range(n):
        for j in range(i+1, n):
            if graph[i][j]:
                edge[i][j] = 1
                edge[j][i] = 1

    m = len(initial)
    ans = n
    cnt = float('inf')
    visit = dict()
    for node in initial:
        visit[node] = 1

    for i in range(m):

        stack = initial[:]
        k = stack.pop(i)
        visit_cur = visit.copy()
        del visit_cur[k]

        while stack:
            nex = []
            for cur in stack:
                for node in 

[Ryanbaiyansong]

··· class UF: def init(self, n): self.f = list(range(n)) self.size = [1] * n

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

    return self.f[x]

def union(self, x, y):
    fx, fy = self.find(x), self.find(y)
    if fx == fy: return 
    if self.size[fx] < self.size[fy]:
        fx, fy = fy, fx 
    self.size[fx] += self.size[fy]
    self.f[fy] = fx

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

n nodes, n * n adj mat

    # i <-> j if v = 1
    # 1 1 0 
    # 1 1 0
    # 0 0 1

    n = len(graph)
    uf = UF(n)
    for i, row in enumerate(graph):
        for j, v in enumerate(row):
            if v:
                uf.union(i, j)

    initial.sort()
    d = defaultdict(int)
    for node in initial:
        f_node = uf.find(node)
        d[f_node] += 1
    res = initial[0]
    mx_sz = -inf
    for node in initial:
        f_node = uf.find(node)
        if d[f_node] == 1:
            sz = uf.size[f_node]
            if sz > mx_sz:
                mx_sz = sz
                res = node
            elif sz == mx_sz:
                res = min(res, node)

    return res

···

[zjsuper]

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]

[ringo1597]

代码

class Solution {
    public int minMalwareSpread(int[][] graph, int[] initial) {
        // 1. Color each component.
        // colors[node] = the color of this node.

        int N = graph.length;
        int[] colors = new int[N];
        Arrays.fill(colors, -1);
        int C = 0;

        for (int node = 0; node < N; ++node)
            if (colors[node] == -1)
                dfs(graph, colors, node, C++);

        // 2. Size of each color.
        int[] size = new int[C];
        for (int color: colors)
            size[color]++;

        // 3. Find unique colors.
        int[] colorCount = new int[C];
        for (int node: initial)
            colorCount[colors[node]]++;

        // 4. Answer
        int ans = Integer.MAX_VALUE;
        for (int node: initial) {
            int c = colors[node];
            if (colorCount[c] == 1) {
                if (ans == Integer.MAX_VALUE)
                    ans = node;
                else if (size[c] > size[colors[ans]])
                    ans = node;
                else if (size[c] == size[colors[ans]] && node < ans)
                    ans = node;
            }
        }

        if (ans == Integer.MAX_VALUE)
            for (int node: initial)
                ans = Math.min(ans, node);

        return ans;
    }

    public void dfs(int[][] graph, int[] colors, int node, int color) {
        colors[node] = color;
        for (int nei = 0; nei < graph.length; ++nei)
            if (graph[node][nei] == 1 && colors[nei] == -1)
                dfs(graph, colors, nei, color);
    }
}

[bookyue]

code

1. union find
2. dfs

    private int[] parent;
    private int[] size;

    public int minMalwareSpread(int[][] graph, int[] initial) {
        int n = graph.length;

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

        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                if (graph[i][j] == 1)
                    union(i, j);

        int[] cnt = new int[n];
        for (int i : initial) cnt[find(i)]++;

        Arrays.sort(initial);
        int max = Integer.MIN_VALUE;
        int ans = initial[0];
        for (int i : initial) {
            int root = find(i);

            if (cnt[root] != 1) continue;

            if (size[root] > max) {
                max = size[root];
                ans = i;
            }
        }

        return ans;
    }

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

    private void union(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);

        if (pRoot == qRoot) return;

        if (size[pRoot] >= size[qRoot]) {
            parent[qRoot] = pRoot;
            size[pRoot] += size[qRoot];
        } else {
            parent[pRoot] = qRoot;
            size[qRoot] += size[pRoot];
        }
    }

    public int minMalwareSpread(int[][] graph, int[] initial) {
        int n = graph.length;

        int[] colors = new int[n];
        Arrays.fill(colors, - 1);
        int color = 0;

        for (int i = 0; i < n; i++)
            if (colors[i] == -1) {
                dfs(graph, colors, i, color);
                color++;
            }

        int[] size = new int[color];
        for (int c : colors) size[c]++;

        int[] cnt = new int[color];
        for (int i : initial) cnt[colors[i]]++;

        Arrays.sort(initial);
        int max = Integer.MIN_VALUE;
        int ans = initial[0];
        for (int i : initial) {
            int c = colors[i];
            if (cnt[c] != 1) continue;

            if (size[c] > max) {
                max = size[c];
                ans = i;
            }
        }

        return ans;
    }

    private void dfs(int[][] graph, int[] colors, int node, int color) {
        colors[node] = color;
        for (int nei = 0; nei < graph.length; nei++)
            if (graph[node][nei] == 1 && colors[nei] == -1)
                dfs(graph, colors, nei, color);
    }

[chenming-cao]

解题思路

并查集。参考官方题解。找到所有的连通分量后，遍历initial数组，看哪些连通分量只包含一个initial中的节点。之后再这样只包含一个initial节点的连通分量中找到包含节点数最多的那个，返回其包含的initial节点即可。如果多个节点满足条件，返回值最小的节点。

代码

class Solution {
    class UnionFind {
        int[] parent;
        int[] size; // store the number of nodes in the connected component

        public UnionFind(int n) {
            parent = new int[n];
            // initialize parent, every node is a root
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
            size = new int[n];
            Arrays.fill(size, 1); // each node is a connected component
        }

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

        public void union(int i1, int i2) {
            // save find(i1) and find(i2) as find(i1) and find(i2) will change after union
            int x = find(i1);
            int y = find(i2);
            parent[x] = y;
            // update size;
            size[y] += size[x];
        }
        // get the number of nodes in the connected component
        public int size(int i) {
            return size[find(i)];
        }

    }
    public int minMalwareSpread(int[][] graph, int[] initial) {
        int n = graph.length; // number of nodes
        UnionFind uf = new UnionFind(n);
        // union
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (graph[i][j] == 1) {
                    uf.union(i, j);
                }
            }
        }
        // sort initial because the node with lower index will be returned 
        // given other conditions are the same
        Arrays.sort(initial);
        // record the number of nodes from initial in each of the connected component
        int[] count = new int[n];
        for (int node : initial) {
            count[uf.find(node)]++;
        }

        int res = -1, resSize = 0;
        for (int node : initial) {
            int root = uf.find(node);
            // from the connected components with only 1 initial node
            // find the one with largest size
            // that initial node will be the result
            int rootSize = uf.size(root);
            if (count[root] == 1 && rootSize > resSize) {
                    res = node;
                    resSize = rootSize;
            } 
        }
        return res != -1 ? res : initial[0];
    }
}

复杂度分析

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

[jackgaoyuan]

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
}

[Abby-xu]

抄答案

class Solution: def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int: n, fa = len(grid), list(range(len(grid))) def find(x): if fa[x]!=x: fa[x] = find(fa[x]) return fa[x] for i in range(n): for j in range(i+1, n): if grid[i][j]: fa[find(j)] = find(i) cnter = Counter(find(i) for i in range(n)) cnter_m = Counter(find(i) for i in mal)
return min([(-cnter[find(i)], i) for i in mal if cnter_m[find(i)]==1] or [(0, min(mal))])[1]

[Elon-Lau]

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

}

[klspta]

class Solution {
    public int minMalwareSpread(int[][] graph, int[] initial) {
        Arrays.sort(initial);
        int N = graph.length;
        int ans = initial[0];
        int max = 0;
        boolean[] init = new boolean[N];
        for (int p : initial) {
            init[p] = true;
        }
        for (int p : initial) {
            init[p] = false;
            int count = process(graph, p, new boolean[N], init);
            if (count > max) {
                max = count;
                ans = p;
            }
            init[p] = true;
        }
        return ans;
    }

    private int process(int[][] graph, int p, boolean[] visited, boolean[] initial) {
        if (initial[p]) {
            return 0;
        }
        visited[p] = true;
        int count = 1;
        for (int q = 0; q < graph[p].length; q++) {
            if (!visited[q] && graph[p][q] == 1) {
                int c = process(graph, q, visited, initial);
                if (c == 0) {
                    return 0;
                }
                count += c;
            }
        }
        return count;
    }
}

[paopaohua]

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];
                }
            }

        }

    }
}

[RestlessBreeze]

code

class Solution {
    public int minMalwareSpread(int[][] graph, int[] initial) {
        int n = graph.length;
        UFind uf = new UFind(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[] cnt = new int[n];
        Map<Integer,Integer> map = new HashMap<>();
        for(int x:initial){
           int rootx = uf.find(x);
           if(map.containsKey(rootx)){
               cnt[x] = 0;
               cnt[map.get(rootx)] = 0;
           }else{
               cnt[x] = uf.getSize(rootx);
           }
           map.put(rootx,x);
        }
        int max = -1;
        int ans = -1;
        for(int x:initial){
            if(cnt[x]>max){
                max = cnt[x];
                ans = x;
            }else if(cnt[x] == max){
                ans = Math.min(ans,x);
            }
        }
        return ans;
    }

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

        public UFind(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){
            int rootx = find(x);
            return size[rootx];
        }

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

        public void union(int x,int y){
            int rootx = find(x);
            int rooty = find(y);
            if(rootx != rooty){
                if(size[rootx]>=size[rooty]){
                    parent[rooty] = rootx;
                    size[rootx] += size[rooty];
                }else{
                    parent[rootx] = rooty;
                    size[rooty] += size[rootx];
                }
            }
        }

    }
}

[Jetery]

代码 (cpp)

class UnionFind {
public:
    UnionFind(int len) {
        parent.resize(len, -1);
    }
    int findRootParent(int p) {
        if (parent[p] == -1 || p == parent[p]) return p;
        return findRootParent(parent[p]);
    }
    void unionConn(int p1, int p2) {
        int p1Root = findRootParent(p1);
        int p2Root = findRootParent(p2);
        if (p1Root != p2Root) {

            parent[p1Root] = p2Root;
        }
    }

private:
    vector<int> parent;
};

class Solution {
public:
    static bool cmp(vector<int>& l, vector<int>& r) {
        return l[1] > r[1] || (l[1] == r[1] && l[0] < r[0]);
    }

    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
        int rowLen = graph.size();
        if (rowLen == 0) {
            return 0;
        }
        int colLen = graph[0].size();
        if (colLen == 0) {
            return 0;
        }
        UnionFind uf(rowLen);
        for (int row = 0; row < rowLen; ++row) {
            for (int col = 0; col < colLen; ++col) {
                if (graph[row][col] == 1) {
                    uf.unionConn(row, col);
                }
            }
        }
        unordered_map<int, int> rootNum;
        for (int i = 0; i < rowLen; ++i) {
            int rootP = uf.findRootParent(i);
            ++rootNum[rootP];
        }
        vector<int> color(rowLen);
        vector<int> groupNum(rowLen, -1);
        for (int i = 0; i < rowLen; ++i) {
            int rootP = uf.findRootParent(i);
            color[i] = rootP;
            groupNum[i] = rootNum[rootP];
        }
        map<int, int> nodeNumPerColor;
        for (int i = 0; i < initial.size(); ++i) {
            ++nodeNumPerColor[color[initial[i]]];
        }
        vector<vector<int>> ans;
        for (int num: initial) {
            if (nodeNumPerColor[color[num]] == 1) {               
                ans.push_back({num, groupNum[num]});
                continue;
            }
            ans.push_back({num, 0});
        }
        sort(ans.begin(), ans.end(), cmp);
        if (!ans.empty()) {
            return ans.at(0).at(0);
        }
        return 0;
    }
};

[Elsa-zhang]

# 924. 尽量减少恶意软件的传播
''' graph[i][j] = 1 时, 每个节点 i 能够直接连接到另一个节点 j
    有bug
'''
import collections

class Solution:
    def minMalwareSpread(self, graph: list[list[int]], initial: list[int]):

        def find(index):
            if parent[index] != index:
                parent[index] = find(parent[index])
            return parent[index] 

        def union(i, j):
            parent_i, parent_j = find(i), find(j)
            parent[parent_i] = parent_j
            sz[j] += sz[i]

        def size(index):
            return sz[find(index)]

        nums = len(graph)
        parent = list(range(len(graph)))
        sz = [1] * nums

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

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

        return ans[1]

graph = [[1,0,0,1,1,0,1,0],[0,1,0,0,0,0,0,1],[0,0,1,0,0,1,0,0],[1,0,0,1,0,0,0,0],[1,0,0,0,1,0,0,0],[0,0,1,0,0,1,0,1],[1,0,0,0,0,0,1,0],[0,1,0,0,0,1,0,1]]
initial = [2,0]

s = Solution()
ans = s.minMalwareSpread(graph, initial)
print(ans)

[mayloveless]

思路

参考官解

代码

/**
 * @param {number[][]} graph
 * @param {number[]} initial
 * @return {number}
 */
var minMalwareSpread = function(graph, initial) {
    const father = Array.from(graph, (v, i) => i);
    function find(v) {
        if (v === father[v]) {
            return v;
        }
        father[v] = find(father[v]);
        return father[v];
    }
    function union(x, y) {
        if (find(x) !== find(y)) {
            father[x] = find(y);
        }
    }

    for (let i = 0; i < graph.length; i++) {
        for (let j = 0; j < graph[0].length; j++) {
            if (graph[i][j]) {
                union(i, j);
            }
        }
    }

    // 计算每个节点的个数
    let counts = graph.reduce((acc, cur, index) => {
        let root = find(index);
        if (!acc[root]) {
            acc[root] = 0;
        }
        acc[root]++;
        return acc;
    }, {});

    // 从最小的找起
    initial.sort((a, b) => a - b);
    let res = initial[0];
    let count = -Infinity;
    initial
        .map((v) => find(v))
        .forEach((item, index, arr) => {
            if (arr.indexOf(item) === arr.lastIndexOf(item)) {
                // 找一个多的
                if (count === -Infinity || counts[item] > count) {
                    res = initial[index];
                    count = counts[item];
                }
            }
        });

  return res;
}

复杂度

时间：O(n^2) 空间：O(d)。

[snmyj]

static int min(const int a, const int b){
    return a < b ? a : b;
}
void init(int* set, int* num,int len){
    for (int i = 0; i < len; i++){
        set[i] = i;
        num[i] = 1;
    }
}

int find(int* set, int x){
    if (set[x] != x){
        set[x] = find(set, set[x]);
    }
    return set[x];
}

void unions(int* set, int* num,int x, int y){
    int px = find(set, x);
    int py = find(set, y);
    if (px != py){
        set[px] = py;
        num[px] = num[py] + num[px];
        num[py] = num[px];
    }
}

int getSize(int* set, int* num, int x, int* pa){
    *pa = find(set, x);
    return num[*pa];
}

int minMalwareSpread(int** graph, int graphSize, int* graphColSize, int* initial, int initialSize){
    int* findSet = malloc(graphSize * sizeof(int));
    int* num = malloc(graphSize * sizeof(int));
    init(findSet, num, graphSize);
    for (int i = 0; i < graphSize; i++){
        for (int j = 0; j < graphColSize[i]; j++){
            if (graph[i][j] == 1){
                unions(findSet, num, i, j);
            }
        }
    }
    int max = 0;
    int index = INT_MAX;
    int* finds = malloc((graphSize + 1) * sizeof(int));
    int* ele = malloc((graphSize + 1) * sizeof(int));
    memset(finds, 0,  (graphSize + 1) * sizeof(int));
    memset(ele, 0,  (graphSize + 1) * sizeof(int));
    int pa = 0;
    int mins = graphSize;
    for (int i = 0; i < initialSize; i++){
        mins = min(initial[i], mins);
        int sz = getSize(findSet, num, initial[i], &pa);
        if (finds[pa] == 0){
            finds[pa] = sz;
            ele[pa] = initial[i];
        }else if (finds[pa] > 0){
            finds[pa] = -1;
        }
    }
    for (int i = 0; i <= graphSize; i++){
        if (finds[i] > max){
            max = finds[i];
            index = ele[i];
        }else if (finds[i] == max){
            index = min(ele[i], index);
        }
    }
    if (max == 0){
        return mins;
    }
    return index;
}

[tiandao043]

思路

并查集，先上色，在被感染的联通分量中选初始最小的，数量独一其次号最小

代码

class DSU{
public:
    vector<int> p;
    vector<int> sz;

    DSU(int n){
        p.resize(n,-1);
        for(int i=0;i<n;i++){
            p[i]=i;
            // sz.push_back(1);
        }
        sz.resize(n,1);
    }
    int find(int i) {
        if (p[i] != i)
        p[i]=find(p[i]);
        return p[i];
    }
    void unio(int x, int y) {
        int xset = find(x);
        int yset = find(y);
        p[xset] = yset;
        if (xset != yset) 
        {            
            sz[yset]+=sz[xset];
        }           
    }
    int size(int x){
        return sz[find(x)];
    }
};

class Solution {
public:
    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
        int n=graph.size();
        DSU dsu(n);
        sort(initial.begin(), initial.end());
        // cout<<1<<endl;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<graph[0].size();j++){
                if(graph[i][j]==1)
                    dsu.unio(i,j);
            }
        }
        map<int,int> count;
        for(int node:initial){
            count[dsu.find(node)]++;
        }
        int ans=-1,ansSize=-1;
        for(auto node:initial){
            int root=dsu.find(node);
            if(count[root]==1){
                int rootSize=dsu.size(root);
                if(rootSize>ansSize){
                    ansSize=rootSize;
                    ans=node;
                }
                // else if(rootSize==ansSize&&node<ans){
                //     ansSize=rootSize;
                //     ans=node;
                // }
            }
        }
        if(ans==-1){
            // ans=INT_MAX;
            // for(int node:initial)ans=min(ans,node);
            return initial[0];
        }
        return ans;
    }

};

O(N^2) O(N)