C# solution: adjacency matrix, DFS


  • 0
    B
    public class Solution 
    {
        private IList<int> result = new List<int>();
        public IList<int> KillProcess(IList<int> pid, IList<int> ppid, int kill) 
        {
            if (pid.Count == 0) return result;
    
            var n = pid.Count;
            var adjacencyMatrix = new Dictionary<int, HashSet<int>>();
    
            for (int i = 0; i < n; i++)
            {
                if (!adjacencyMatrix.ContainsKey(ppid[i]))   adjacencyMatrix[ppid[i]] = new HashSet<int>();
                if (!adjacencyMatrix.ContainsKey(pid[i]))   adjacencyMatrix[pid[i]] = new HashSet<int>();
    
                adjacencyMatrix[ppid[i]].Add(pid[i]);
            }
    
            if (!adjacencyMatrix.ContainsKey(kill)) return result;
    
            DFS(adjacencyMatrix, kill, 0, false);
    
            return result;
        }
    
        private void DFS(Dictionary<int, HashSet<int>> adjacencyMatrix, int killId, int curId, bool needToKill)
        {
            if (needToKill || curId == killId)
            {
                result.Add(curId);
            }
    
            if (curId == killId || needToKill)
            {
                foreach (var nextId in adjacencyMatrix[curId])
                {
                    DFS(adjacencyMatrix, killId, nextId, true);
                }
            }
            else
            {
                foreach (var nextId in adjacencyMatrix[curId])
                {
                    DFS(adjacencyMatrix, killId, nextId, false);
                }            
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.