Dear reader, welcome to the article on the problem named "Spread of Infection" . It is a simple application of the BFS traversal algor
- Given an undirected graph representing people and their connectivity. Vertices 0 to n-1 represent different people and edge (u, v) represents that there can be a direct contact between persons u and v.
- You are given a src person, who got infected by a disease at time t = 0.
- You are also given the total time t during which the infection can spread among the people.
- If a person is infected, then it takes 1 unit of time to make all of it's connections get infected.
- You need to find the count of people who can get infected by the disease within the time t.
Note: Input is given in the form of adjacency list.
- The idea is to use a BFS traversal algorithm with the source node as the src.
- Along with the source node's value, we will also push the visiting time t = 0.
- We will maintain a count integer variable set to 0 initially, which will finally store the result, i.e. number of infected people within the total time of spread of infection.
- We will run the BFS, until the queue becomes empty (all nodes get visited), or the visiting time of the front element becomes greater than the total time given.
- If the node is already visited (cycle exists and the node was visited with a smaller visiting time), then we will simply pop and continue for the next element (do not visit it's neighbours).
- Otherwise, we will mark the current node as visited. For each element, who's visiting time < total time, which gets removed (popped) from the queue, we will increment the count by 1.
- Also, we will break from the BFS traversal, if the front element's visiting time is greater than the total time of spread.
Note: We can simply break because all the nodes after the front element present in the queue, will have visiting time greater than (or equal to) the visiting time of the front element. Since, the front element has time > t, hence all the elements after it will also have time > t.
- Now, we will push all the unvisited neighbours of the current node with visiting time one more than the visiting time of the current node. (If visiting time of src is x, then it's neighbours will have visiting time x + 1).
- Finally, when the BFS algorithm is successfully completed, we can simply print the value of count.
Note: Before reading the Code, we recommend that you must try to come up with the solution on your own. Now, hoping that you have tried by yourself, here is the Java code.