(This problem is the same as Minimize Malware Spread, with the differences bolded.)
In a network of nodes, each node i is directly connected to another node j if and only if graph[i][j] = 1.
Some nodes initial are initially infected by malware.  Whenever two nodes are directly connected and at least one of those two nodes is infected by malware, both nodes will be infected by malware.  This spread of malware will continue until no more nodes can be infected in this manner.
Suppose M(initial) is the final number of nodes infected with malware in the entire network, after the spread of malware stops.
We will remove one node from the initial list, completely removing it and any connections from this node to any other node.  Return the node that if removed, would minimize M(initial).  If multiple nodes could be removed to minimize M(initial), return such a node with the smallest index.
 



Example 1:
Input: graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
Output: 0


Example 2:
Input: graph = [[1,1,0],[1,1,1],[0,1,1]], initial = [0,1]
Output: 1


Example 3:
Input: graph = [[1,1,0,0],[1,1,1,0],[0,1,1,1],[0,0,1,1]], initial = [0,1]
Output: 1

 
Note:

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

Source: leetcode | Difficulty: MEDIUM
Tags: Matrices

Data structures

Graph traversal

Spanning trees

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

Solutions:
from collections import deque

class Solution:

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

		def bfs(graph, seed, removed):
			queue = deque(seed)
			visited = seed
			while len(queue) > 0:
				node = queue.popleft()
				for next_node in range(len(graph[node])):
					if graph[node][next_node] == 0 or next_node in visited or next_node == removed:
						continue
					visited.add(next_node)
					queue.append(next_node)
			return len(visited)
		best = len(graph)
		best_remove = initial[0]
		initial = set(initial)
		for remove_node in initial:
			initial_removed = initial - {remove_node}
			node_result = bfs(graph, initial_removed, remove_node)
			if node_result < best or (node_result == best and best_remove > remove_node):
				best = node_result
				best_remove = remove_node
		return best_remove


class Solution:

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

		def dfs(i, s):
			if i in visit or (i in ht and i != s):
				return
			visit.add(i)
			source[i].append(s)
			for j in graph[i]:
				dfs(j, s)
		ht = set(initial)
		for i in range(len(graph)):
			tmp = []
			for j in range(len(graph[i])):
				if graph[i][j]:
					tmp.append(j)
			graph[i] = tmp
		source = [[] for _ in range(len(graph))]
		for i in initial:
			visit = set()
			dfs(i, i)
		dic = collections.defaultdict(int)
		for i in range(len(source)):
			if len(source[i]) == 1:
				dic[source[i].pop()] += 1
		(res, val) = (len(graph), 0)
		for (i, cnt) in list(dic.items()):
			if cnt > val:
				(res, val) = (i, cnt)
			elif cnt == val:
				res = min(res, i)
		return res


import collections

class Solution:

	def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
		numNodes = len(graph)
		minSpread = float('inf')
		minNode = None
		initial.sort()
		for i in initial:
			visited = set([i])
			for j in initial:
				self.helper(graph, j, visited)
			if len(visited) < minSpread:
				minSpread = len(visited)
				minNode = i
		return minNode

	def helper(self, graph, curr, visited):
		if curr in visited:
			return
		edges = graph[curr]
		visited.add(curr)
		for i in range(len(edges)):
			if graph[curr][i] == 1:
				self.helper(graph, i, visited)


class Solution:

	def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
		table = {}
		for i in range(len(graph)):
			table[i] = []
		for i in range(len(graph)):
			for j in range(i + 1, len(graph[i])):
				if graph[i][j] == 1:
					table[i].append(j)
					table[j].append(i)
		print(table)

		def DFS(n, exclude_node):
			for connect_node in table[n]:
				if connect_node not in self.visited and connect_node != exclude_node:
					self.visited.append(connect_node)
					DFS(connect_node, exclude_node)
		res = []
		current_max = 0
		for node in initial:
			exclude = node
			self.visited = []
			for i in range(len(initial)):
				if initial[i] != exclude:
					if initial[i] not in self.visited:
						self.visited.append(initial[i])
					DFS(initial[i], node)
			left = len(graph) - len(self.visited)
			if left > current_max:
				res = [node]
				current_max = left
			elif left == current_max:
				res.append(node)
			print((node, self.visited))
		res.sort()
		print(res)
		return res[0]


class Solution:

	def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
		n = len(graph)
		d = collections.defaultdict(list)
		for init in initial:
			vis = set(initial)
			Q = collections.deque([init])
			while Q:
				infect = Q.popleft()
				for node in range(len(graph[infect])):
					if graph[infect][node] == 0:
						continue
					if node in vis:
						continue
					vis.add(node)
					d[node].append(init)
					Q.append(node)
		res = [0] * n
		for key in d:
			if len(d[key]) == 1:
				res[d[key][0]] += 1
		if max(res) == 0:
			return min(initial)
		return res.index(max(res))


class Solution:

	def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
		index = 0
		count = len(graph)
		initial.sort()

		def search(removed):
			visited = set()
			dfs = []
			for i in initial:
				if i != removed:
					dfs.append(i)
			while dfs:
				curr = dfs.pop()
				if curr in visited:
					continue
				visited.add(curr)
				for (n, i) in enumerate(graph[curr]):
					if n == removed:
						continue
					if i:
						dfs.append(n)
			return len(visited)
		for i in initial:
			z = search(i)
			if z < count:
				index = i
				count = z
		return index


class Solution:

	def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
		n = len(graph)
		parent = list(range(n))
		size = [1] * n

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

		def union(u, v):
			(x, y) = (find(u), find(v))
			if x != y:
				parent[y] = x
				size[x] += size[y]
		graph = [[v for (v, x) in enumerate(row) if x and u != v] for (u, row) in enumerate(graph)]
		infected = [False] * n
		for u in range(n):
			if u in initial:
				infected[u] = True
		for u in range(n):
			if not infected[u]:
				for v in graph[u]:
					if not infected[v]:
						union(u, v)
		threat = defaultdict(set)
		for u in range(n):
			if not infected[u]:
				for v in graph[u]:
					if infected[v]:
						threat[find(u)].add(v)
		best = 0
		best_idx = -1
		for v in sorted(initial):
			preventable = set()
			for u in graph[v]:
				if len(threat[find(u)]) == 1:
					preventable.add(find(u))
			total = 1 + sum((size[u] for u in preventable))
			if total > best:
				best = total
				best_idx = v
		return best_idx


from collections import defaultdict, Counter

class UF:

	def __init__(self, keys):
		self.uf = {}
		for key in keys:
			self.uf[key] = key

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

	def union(self, x, y):
		xx = self.find(x)
		yy = self.find(y)
		self.uf[xx] = yy

class Solution:

	def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
		initial.sort()
		malware = set(initial)
		uf = UF(range(len(graph)))
		neighbors = defaultdict(set)
		for i in range(len(graph)):
			for j in range(len(graph[i])):
				if graph[i][j] == 0:
					continue
				elif i in malware and j in malware:
					continue
				elif i in malware:
					neighbors[i].add(j)
				elif j in malware:
					neighbors[j].add(i)
				else:
					uf.union(i, j)
		components = Counter([uf.find(x) for x in range(len(graph)) if x not in malware])
		infected = defaultdict(set)
		incoming = defaultdict(set)
		for (key, value) in neighbors.items():
			infected[key] = set([uf.find(x) for x in value])
			for component in infected[key]:
				incoming[component].add(key)
		ret = initial[0]
		score = 0
		for mal in initial:
			mal_score = 0
			for component in infected[mal]:
				if len(incoming[component]) == 1:
					mal_score += components[component]
			if mal_score > score:
				score = mal_score
				ret = mal
		print(components, neighbors, infected, incoming)
		return ret


class UF:

	def __init__(self, n):
		self.arr = list(range(n + 1))
		self.rank = [1] * (n + 1)

	def root(self, x):
		curr = x
		while curr != self.arr[curr]:
			curr = self.arr[curr]
		return curr

	def union(self, x, y):
		root_x = self.root(x)
		root_y = self.root(y)
		rank_x = self.rank[root_x]
		rank_y = self.rank[root_y]
		if rank_x >= rank_y:
			self.arr[root_y] = root_x
			self.rank[root_x] += rank_y
		else:
			self.arr[root_x] = root_y
			self.rank[root_y] += rank_x

class Solution:

	def dfs(self, root, seen, uf, intersection):
		for (i, v) in enumerate(self.graph[root]):
			if v == 0:
				continue
			if i in self.init_set:
				if root not in intersection:
					intersection[root] = []
				intersection[root].append(i)
				continue
			uf.union(root, i)
			if i in seen:
				continue
			seen.add(i)
			self.dfs(i, seen, uf, intersection)

	def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
		self.graph = graph
		self.init_set = set(initial)
		initial.sort()
		uf = UF(len(graph[0]))
		seen = set()
		intersection = {}
		for node in range(len(graph[0])):
			if node in self.init_set:
				continue
			self.dfs(node, seen, uf, intersection)
		islands = {}
		for node in range(len(graph[0])):
			root = uf.root(node)
			if root not in islands:
				islands[root] = set()
			if node in intersection:
				for elt in intersection[node]:
					islands[root].add(elt)
		islandCounts = {}
		for node in range(len(graph[0])):
			root = uf.root(node)
			if len(islands[root]) == 1:
				for key in islands[root]:
					if key not in islandCounts:
						islandCounts[key] = 1
					else:
						islandCounts[key] += 1
		if len(islandCounts) == 0:
			return initial[0]
		res = sorted(islandCounts, key=lambda x: (-islandCounts[x], x))
		return res[0]


class Solution:

	def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
		conn = collections.defaultdict(set)
		n = len(graph)
		visited = [False] * n
		for i in initial:
			visited[i] = True

		def bfs(node):
			q = collections.deque([node])
			v = visited[:]
			while q:
				i = q.popleft()
				for (j, k) in enumerate(graph[i]):
					if k and (not v[j]):
						v[j] = True
						q.append(j)
						conn[j].add(node)
		for i in initial:
			bfs(i)
		cnt = collections.Counter()
		for (k, v) in list(conn.items()):
			if len(v) == 1:
				cnt[v.pop()] += 1
		if not cnt:
			return min(initial)
		s = sorted(list(cnt.items()), key=lambda k: (k[1], -k[0]))
		return s[-1][0]


class Solution(object):

	def minMalwareSpread(self, graph, initial):
		N = len(graph)
		clean = set(range(N)) - set(initial)

		def dfs(u, seen):
			for (v, adj) in enumerate(graph[u]):
				if adj and v in clean and (v not in seen):
					seen.add(v)
					dfs(v, seen)
		infected_by = {v: [] for v in clean}
		for u in initial:
			seen = set()
			dfs(u, seen)
			for v in seen:
				infected_by[v].append(u)
		contribution = collections.Counter()
		for (v, neighbors) in infected_by.items():
			if len(neighbors) == 1:
				contribution[neighbors[0]] += 1
		best = (-1, min(initial))
		for (u, score) in contribution.items():
			if score > best[0] or (score == best[0] and u < best[1]):
				best = (score, u)
		return best[1]


class Solution:

	def dfs(self, i, visited, graph):
		if i in visited:
			return
		visited.add(i)
		for (x, edge) in enumerate(graph[i]):
			if edge:
				self.dfs(x, visited, graph)

	def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
		numInfected = float('inf')
		minVal = None
		initial.sort()
		for i in initial:
			visited = set([i])
			for j in initial:
				self.dfs(j, visited, graph)
			if len(visited) < numInfected:
				numInfected = len(visited)
				minVal = i
		return minVal


from collections import defaultdict

class Solution:

	def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
		if not graph:
			return -1
		n = len(graph)
		initial = sorted(initial)
		clean = set([i for i in range(n)]) - set(initial)
		infected_by = {i: [] for i in range(n)}

		def dfs(node):
			for (i, v) in enumerate(graph[node]):
				if v and i in clean and (i not in seen):
					seen.add(i)
					dfs(i)
		for node in initial:
			seen = set()
			dfs(node)
			for u in seen:
				infected_by[u].append(node)
		cnt = {v: 0 for v in initial}
		for i in infected_by:
			if len(infected_by[i]) == 1:
				cnt[infected_by[i][0]] += 1
		m = 0
		res = initial[0]
		for i in cnt:
			if cnt[i] > m:
				res = i
				m = cnt[i]
		return res


class Solution:

	def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
		nodes = len(graph)
		min_count = float('inf')
		min_node = 0
		for node in sorted(initial):
			visited = set()
			queue = deque()
			count = 0
			for i in initial:
				if i != node and i not in visited:
					queue.append(i)
					visited.add(i)
					count += 1
					while queue:
						curr = queue.popleft()
						for (i, edge) in enumerate(graph[curr]):
							if edge == 1 and i != node and (i not in visited):
								queue.append(i)
								visited.add(i)
								count += 1
			if count < min_count:
				min_count = count
				min_node = node
		return min_node


class Solution:

	def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
		spreads = [[] for _ in range(len(graph))]
		initial = set(initial)
		for i in initial:
			q = {i}
			visited = set()
			while q:
				cur = q.pop()
				if cur in visited or (cur in initial and cur != i):
					continue
				visited.add(cur)
				spreads[cur].append(i)
				for j in range(len(graph[cur])):
					if graph[cur][j]:
						q.add(j)
		counts = defaultdict(int)
		for s in spreads:
			if len(s) == 1:
				counts[s[0]] += 1
		most = next(iter(initial))
		for (i, c) in list(counts.items()):
			if c > counts[most] or (c == counts[most] and i < most):
				most = i
		return most


class Solution:

	def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
		bfs = []
		oinitial = set(initial)
		for i in initial:
			bfs.append([i, i])
		frm = {}
		for init in initial:
			seen = set(initial)
			bfs = [init]
			for n in bfs:
				for (i, c) in enumerate(graph[n]):
					if i == n or i in seen or c == 0:
						continue
					seen.add(i)
					if i in frm:
						frm[i].append(init)
					else:
						frm[i] = [init]
					bfs.append(i)
		res = [0] * len(graph)
		for k in frm:
			if len(frm[k]) == 1:
				res[frm[k][0]] += 1
		if max(res) == 0:
			return min(initial)
		return res.index(max(res))


class Solution:

	def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
		d = collections.defaultdict(list)
		for init in initial:
			visit = set(initial)
			q = collections.deque([init])
			while q:
				node = q.popleft()
				for i in range(len(graph[node])):
					if graph[node][i] == 0 or i in visit:
						continue
					visit.add(i)
					d[i].append(init)
					q.append(i)
		res = [0] * len(graph)
		for m in d:
			if len(d[m]) == 1:
				res[d[m][0]] += 1
		if max(res) == 0:
			return min(initial)
		return res.index(max(res))


from functools import lru_cache
from typing import List, Tuple
import numpy
import collections

class Solution:

	def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
		const_n = len(graph)
		d = collections.defaultdict(list)
		for init in initial:
			vis = set(initial)
			q = collections.deque([init])
			while q:
				index = q.popleft()
				for node in range(len(graph[index])):
					if graph[index][node] == 0:
						continue
					if node in vis:
						continue
					vis.add(node)
					d[node].append(init)
					q.append(node)
				pass
			pass
		res = [0] * const_n
		for (key, value) in d.items():
			if len(value) == 1:
				res[value[0]] += 1
		if max(res) == 0:
			return min(initial)
		return res.index(max(res))


from collections import Counter, defaultdict

class Solution:

	def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
		N = len(graph)
		seen = set()
		refcounter = Counter()
		clean_nodes = set(range(N)) - set(initial)
		maxval = 0

		def dfs(node, seen):
			for (v, adj) in enumerate(graph[node]):
				if adj and v not in seen and (v in clean_nodes):
					seen.add(node)
					dfs(v, seen)
		for key in initial:
			seen = set()
			dfs(key, seen)
			refcounter[key] = len(seen)
			if maxval < refcounter[key]:
				maxval = refcounter[key]
			seen.clear()
		print(refcounter)
		maxlist = [key for (key, val) in list(refcounter.items()) if refcounter[key] == maxval]
		if not maxlist or len(maxlist) > 1:
			return sorted(initial)[0]
		return maxlist[0]


class Solution:

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

		def infected(src, exclude=None):
			infected = set()

			def dfs(node, infected):
				if node in infected:
					return
				infected |= {node}
				for neighbor in range(len(graph[node])):
					if graph[node][neighbor] == 0 or neighbor == exclude:
						continue
					dfs(neighbor, infected)
			for source in src:
				if source == exclude:
					continue
				dfs(source, infected)
			return len(infected)
		initial.sort()
		(res, best) = (initial[0], len(graph))
		for source in initial:
			temp = infected(initial, source)
			if temp < best:
				(res, best) = (source, temp)
		return res


class Solution:

	def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
		least_infections = len(graph)
		node_to_remove = initial[0]
		for i in initial:
			total_infected = 0
			q = initial[:]
			q.remove(i)
			visited = set()
			while q != []:
				v = q.pop()
				if v != i and (not v in visited):
					total_infected += 1
					visited.add(v)
					for (j, edge) in enumerate(graph[v]):
						if j != i and edge == 1 and (not j in visited):
							q.append(j)
			if total_infected < least_infections:
				least_infections = total_infected
				node_to_remove = i
			elif total_infected == least_infections:
				node_to_remove = min(i, node_to_remove)
		return node_to_remove