# ---
# title: 924. Minimize Malware Spread
# id: problem924
# author: Tian Jun
# date: 2020-10-31
# difficulty: Hard
# categories: Depth-first Search, Union Find
# link: <https://leetcode.com/problems/minimize-malware-spread/description/>
# hidden: true
# ---
# 
# 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.  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.
# 
# Note that if a node was removed from the `initial` list of infected nodes, it
# may still be infected later as a result of the malware spread.
# 
# 
# 
# **Example 1:**
# 
#     
#     
#     Input: graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
#     Output: 0
#     
# 
# **Example 2:**
# 
#     
#     
#     Input: graph = [[1,0,0],[0,1,0],[0,0,1]], initial = [0,2]
#     Output: 0
#     
# 
# **Example 3:**
# 
#     
#     
#     Input: graph = [[1,1,1],[1,1,1],[1,1,1]], initial = [1,2]
#     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`
# 
# 
## @lc code=start
using LeetCode

## add your code here:
## @lc code=end
