Screen Shot Thene are zombies in Seattle. Liv and Ravi are trying to track them

Question

Screen Shot Thene are zombies in Seattle. Liv and Ravi are trying to track them down to find out who is creating new zombies in an effort to prevent an apocalypse. Other than the patient-zero zombies who became so by mixing MaxRager and tainted Utopium) new people only become zombies after being scratched by an existing zombie. Zombism is transitive. This means that a zombie 0 knows zombie 1 and zombie 1 knows zombie 2 then zombie O is connected to zombie 2 by way of knowing zombie 1.A zombie cluster is a group of zombies who are directly or indirectly linked through the other zombies they know, such as the one who scratched them or supplies who them with brains The diagram showing connectedness will be made up of a number of binary strings, characters 0 or 1. Each of the characters in the string represents a row element is connected to the zomble at that character's index. For instance, a zombie O with a connectedness zombie 2. The complete matrix of zombie connectedness is whether the zombie associated with string 110' is connected to zombies O iself) and zombie 1, but not to 110 ee1

Explanation / Answer

This Problem is Similar to finding the Number of a strongly connected component in a graph.For this, we can use DFS.

Algorithm

We visit each vertex, traverse all its neighbors and mark them as visited. When there is no neighbor left we increment cluster count and backtrack to next node.

example code(in python)

For this example, the output is: 2

THUMBS UP IF YOU ARE SATISFIED WITH THE ANSWER OTHERWISE REPLY WITH YOUR CONCERN.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.