DDSA
Advertisement

928. Minimize Malware Spread II

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