【Leetcode】并查集/DFS/BFS多解

题目-Leetcode 924

给出了一个由 n 个节点组成的网络，用 n × n 个邻接矩阵图 graph 表示。在节点网络中，当 graph[i][j] = 1 时，表示节点 i 能够直接连接到另一个节点 j。 一些节点 initial 最初被恶意软件感染。只要两个节点直接连接，且其中至少一个节点受到恶意软件的感染，那么两个节点都将被恶意软件感染。这种恶意软件的传播将继续，直到没有更多的节点可以被这种方式感染。假设 M(initial) 是在恶意软件停止传播之后，整个网络中感染恶意软件的最终节点数。如果从 initial 中移除某一节点能够最小化 M(initial)， 返回该节点。如果有多个节点满足条件，就返回索引最小的节点。请注意，如果某个节点已从受感染节点的列表 initial 中删除，它以后仍有可能因恶意软件传播而受到感染。

并查集思路

被感染节点数等于 1  只需要恢复该被感染节点，整个连通子图将恢复正常；

被感染节点数大于 1  就算恢复该被感染节点，整个连通子图也无法恢复正常；

寻找中只有1个感染节点的最大连通子图

from collections import defaultdict

class UnionFind:
    def __init__(self, n):
        self.root = [i for i in range(n)]
        self.size = [1]*n
        self.part = n

    def find(self, x):
        if x != self.root[x]:
            # 在查询的时候合并到顺带直接根节点
            root_x = self.find(self.root[x])
            self.root[x] = root_x
            return root_x
        return x

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y: return
        if self.size[root_x] >= self.size[root_y]:
            root_x, root_y = root_y, root_x
        self.root[root_x] = root_y
        self.size[root_y] += self.size[root_x]   # 将x合并在y中
        self.size[root_x] = 0   # 将非根节点的秩赋 0
        self.part -= 1          # 记录根节点个数
        return

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

    def get_root_part(self):
        # 获取每个根节点对应的组
        part = defaultdict(list)
        n = len(self.root)
        for i in range(n):
            part[self.find(i)].append(i)
        return part

    def get_root_size(self):
        # 获取每个根节点对应的组大小
        size = defaultdict(int)
        n = len(self.root)
        for i in range(n):
            size[self.find(i)] = self.size[self.find(i)]
        return size


class Solution:
    def minMalwareSpread(self, graph, initial):
        n = len(graph)
        uf = UnionFind(n)   # 创建初始集合
        for i in range(n):  # 遍历连接关系合并部分集合
            for j in range(i):
                if graph[i][j]: uf.union(i, j)

        maxlen, idx = -1, -1
        virus = set(initial)
        parts = uf.get_root_part()  # 合并后每个集合的元素
        for root in parts:             # 遍历每个集合
            cnt, length = 0, 0
            for i in parts[root]:      # 遍历同个集合中的每个元素
                length += 1
                if i in virus:
                    cnt += 1
                    cur = i
            if cnt == 1:               # 只有一个感染节点
                if length > maxlen:
                    maxlen = length
                    idx = cur 
                elif length == maxlen:  # 相同长度选序号更小的
                    idx = min(idx, cur)

        if idx==-1: idx = min(initial)  # 没有只感染一个节点的集合
        return idx

DFS思路

记录下已访问过的节点，该集合的元素个数以及该集合中初始感染的元素；

from collections import defaultdict

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

        n = len(graph)
        edge = defaultdict(list)         # 构建邻接表
        for i in range(n):
            for j in range(i):
                if graph[i][j]:
                    edge[i].append(j)    # 双向
                    edge[j].append(i)

        visited = [False] * n
        initial = set(initial)

        def dfs(node, length, cnt):
            length += 1
            visited[node] = True
            if node in initial: 
                cnt += 1
            if node in edge:
                for nxt in edge[node]:
                    if not visited[nxt]:
                        length, cnt = dfs(nxt, length, cnt)
                        # length += nxtlength
                        # cnt += nxtcnt
            return length, cnt

        maxlen, idx = -1, -1

        for node in initial:            
            if visited[node]: continue    # 已被访问
            length, cnt = dfs(node, 0, 0)

            if cnt == 1:               # 只有一个感染节点
                if length > maxlen:
                    maxlen = length
                    idx = node 
                elif length == maxlen:  # 相同长度选序号更小的
                    idx = min(idx, node)

        if idx==-1: idx = min(initial)  # 没有只感染一个节点的集合

        return idx

BFS思路

 模拟移除某个节点后，统计被感染的节点数量，取最小感染量对应的移除节点；

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

        n = len(graph)
        edge = defaultdict(list)         # 构建邻接表
        for i in range(n):
            for j in range(i):
                if graph[i][j]:
                    edge[i].append(j)    # 双向
                    edge[j].append(i)

        mincnt, idx = n+1, -1

        for node in initial:            
            cnt = 0
            initial.remove(node)       
            stack = initial[:]           # 假设移除某个节点，统计剩下的节点感染总数
            curnodes = set(stack)        # 便于查找

            while stack:
                tmp = []
                for curnode in stack:
                    for nxt in edge[curnode]:
                        if nxt not in curnodes:   # 没被感染就加入感染
                            curnodes.add(nxt)
                            tmp.append(nxt)
                            cnt += 1
                stack = tmp[:]

            if cnt < mincnt:
                mincnt = min(mincnt, cnt)
                idx = node
            elif cnt == mincnt:
                idx = min(idx, node)

            initial.insert(0,node)         # 还原初始感染节点,必须插入在前侧，否则会影响for循环
            
        return idx