Advertisement
928. Minimize Malware Spread II
UnknownView on LeetCode
928.cs
C#
public class Solution
{
public int MinMalwareSpread(int[][] graph, int[] initial)
{
int ans = 0;
int minCount = graph.Length;
Array.Sort(initial);
foreach (var i in initial)
{
int count = Bfs(graph, i, initial);
if (count < minCount)
{
minCount = count;
ans = i;
}
}
return ans;
}
private int Bfs(int[][] graph, int removed, int[] initial)
{
Queue<int> q = new Queue<int>();
bool[] seen = new bool[graph.Length];
seen[removed] = true;
int count = 0;
foreach (var i in initial)
{
if (i != removed)
{
q.Enqueue(i);
seen[i] = true;
}
}
while (q.Count > 0)
{
int u = q.Dequeue();
++count;
for (int i = 0; i < graph.Length; ++i)
{
if (seen[i])
continue;
if (i != u && graph[i][u] == 1)
{
q.Enqueue(i);
seen[i] = true;
}
}
}
return count;
}
}Advertisement