{"id":"1c1749d4-b9ff-4dd2-869e-676b9b13afa9","name":"Spread Of Infection","description":"1. You are given a graph, representing people and their connectivity.\r\n2. You are also given a src person (who got infected) and time t.\r\n3. You are required to find how many people will get infected in time t, if the infection spreads to neighbors of infected person in 1 unit of time.","inputFormat":"Input has been managed for you","outputFormat":"count of people infected by time t","constraints":"None","sampleCode":{"cpp":{"code":"#include <iostream>\n#include <vector>\n#include <queue>\n\nusing namespace std;\n\nclass Edge\n{\npublic:\n int src = 0;\n int nbr = 0;\n\n Edge(int src, int nbr)\n {\n this->src = src; \n this->nbr = nbr;\n }\n};\n\n\nint main() { \n \n int vtces;\n cin >> vtces;\n vector<vector<Edge>> graph(vtces, vector<Edge>());\n \n\n int edges;\n cin >> edges;\n\n for (int i = 0; i < edges; i++ ) {\n int u, v, w; \n cin >> u >> v >> w;\n \n graph[u].push_back(Edge(u, v));\n graph[v].push_back(Edge(v, u));\n\n } \n int src,t; \n cin >> src;\n cin >> t; \n \n //write your code here \n\n \n return 0;\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n static class Edge {\r\n int src;\r\n int nbr;\r\n\r\n Edge(int src, int nbr) {\r\n this.src = src;\r\n this.nbr = nbr;\r\n }\r\n }\r\n\r\n public static void main(String[] args) throws Exception {\r\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\r\n\r\n int vtces = Integer.parseInt(br.readLine());\r\n ArrayList<Edge>[] graph = new ArrayList[vtces];\r\n for (int i = 0; i < vtces; i++) {\r\n graph[i] = new ArrayList<>();\r\n }\r\n\r\n int edges = Integer.parseInt(br.readLine());\r\n for (int i = 0; i < edges; i++) {\r\n String[] parts = br.readLine().split(\" \");\r\n int v1 = Integer.parseInt(parts[0]);\r\n int v2 = Integer.parseInt(parts[1]);\r\n graph[v1].add(new Edge(v1, v2));\r\n graph[v2].add(new Edge(v2, v1));\r\n }\r\n\r\n int src = Integer.parseInt(br.readLine());\r\n int t = Integer.parseInt(br.readLine());\r\n \r\n // write your code here\r\n }\r\n\r\n}"},"python":{"code":"import threading , queue\nclass Edge:\n def __init__(self,src,nbr,wt):\n self.src = src\n self.nbr = nbr\n self.wt=wt\n\n\ndef main():\n vtces = int(input())\n edges = int(input()) \n graph = {}\n for i in range(vtces):\n graph[i] = []\n \n for i in range(edges): \n lines = input().split(\" \")\n v1=int(lines[0])\n v2=int(lines[1])\n wt=int(lines[2])\n e1 = Edge(v1 ,v2 ,wt)\n e2 = Edge(v2 ,v1 ,wt)\n graph[e1.src].append(e1)\n graph[e2.src].append(e2) \n \n src = int(input()) \n t = int(input()) \n # Write your code here \n \n \nif __name__ == \"__main__\":\n main()"}},"points":10,"difficulty":"easy","sampleInput":"7\r\n8\r\n0 1 10\r\n1 2 10\r\n2 3 10\r\n0 3 10\r\n3 4 10\r\n4 5 10\r\n5 6 10\r\n4 6 10\r\n6\r\n3","sampleOutput":"4","questionVideo":"https://www.youtube.com/embed/3A1XJbRs_6A?end=161","hints":[],"associated":[{"id":"270bde7a-f0de-4ec3-8a89-72fe014da45f","name":"Which data structure is best suited for this problem ?","slug":"which-data-structure-is-best-suited-for-this-problem","type":4},{"id":"57241aa0-baa5-4c1c-8080-9dd0d7722635","name":"Which algorithm a single stack helps us to implement? (Spread Of Infection)","slug":"which-algorithm-a-single-stack-helps-us-to-implement-spread-of-infection","type":4},{"id":"5ad84dc8-cbe7-4447-932b-dd0c26736be1","name":"Which algorithm would you use if you have to reach all the neighbouring nodes first? (Spread Of Infection)","slug":"which-algorithm-would-you-use-if-you-have-to-reach-all-the-neighbouring-nodes-first-spread-of-infection","type":4},{"id":"d25926c4-c502-42eb-b3e7-ccfe3ed6ddea","name":"What is the rate of increase of spread of infection?","slug":"what-is-the-rate-of-increase-of-spread-of-infection","type":4}],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"02ab8fe3-cddd-43ad-b241-b8b1a2fcd52e","name":"Graphs For Beginners","slug":"graphs-for-beginners","type":0},{"id":"d28c9055-3c89-41dd-97a9-7b5ee4f56138","name":"Spread Of Infection","slug":"spread-of-infection","type":1}],"next":{"id":"51dac32b-6457-4a0d-b76a-0709e27b857f","name":"Spread of Infection","type":3,"slug":"spread-of-infection"},"prev":{"id":"a23a17fa-e27f-4dfd-ac4e-bdf6c0687482","name":"Is Graph Bipartite","type":3,"slug":"is-graph-bipartite"}}}

Spread Of Infection

1. You are given a graph, representing people and their connectivity. 2. You are also given a src person (who got infected) and time t. 3. You are required to find how many people will get infected in time t, if the infection spreads to neighbors of infected person in 1 unit of time.

{"id":"1c1749d4-b9ff-4dd2-869e-676b9b13afa9","name":"Spread Of Infection","description":"1. You are given a graph, representing people and their connectivity.\r\n2. You are also given a src person (who got infected) and time t.\r\n3. You are required to find how many people will get infected in time t, if the infection spreads to neighbors of infected person in 1 unit of time.","inputFormat":"Input has been managed for you","outputFormat":"count of people infected by time t","constraints":"None","sampleCode":{"cpp":{"code":"#include <iostream>\n#include <vector>\n#include <queue>\n\nusing namespace std;\n\nclass Edge\n{\npublic:\n int src = 0;\n int nbr = 0;\n\n Edge(int src, int nbr)\n {\n this->src = src; \n this->nbr = nbr;\n }\n};\n\n\nint main() { \n \n int vtces;\n cin >> vtces;\n vector<vector<Edge>> graph(vtces, vector<Edge>());\n \n\n int edges;\n cin >> edges;\n\n for (int i = 0; i < edges; i++ ) {\n int u, v, w; \n cin >> u >> v >> w;\n \n graph[u].push_back(Edge(u, v));\n graph[v].push_back(Edge(v, u));\n\n } \n int src,t; \n cin >> src;\n cin >> t; \n \n //write your code here \n\n \n return 0;\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n static class Edge {\r\n int src;\r\n int nbr;\r\n\r\n Edge(int src, int nbr) {\r\n this.src = src;\r\n this.nbr = nbr;\r\n }\r\n }\r\n\r\n public static void main(String[] args) throws Exception {\r\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\r\n\r\n int vtces = Integer.parseInt(br.readLine());\r\n ArrayList<Edge>[] graph = new ArrayList[vtces];\r\n for (int i = 0; i < vtces; i++) {\r\n graph[i] = new ArrayList<>();\r\n }\r\n\r\n int edges = Integer.parseInt(br.readLine());\r\n for (int i = 0; i < edges; i++) {\r\n String[] parts = br.readLine().split(\" \");\r\n int v1 = Integer.parseInt(parts[0]);\r\n int v2 = Integer.parseInt(parts[1]);\r\n graph[v1].add(new Edge(v1, v2));\r\n graph[v2].add(new Edge(v2, v1));\r\n }\r\n\r\n int src = Integer.parseInt(br.readLine());\r\n int t = Integer.parseInt(br.readLine());\r\n \r\n // write your code here\r\n }\r\n\r\n}"},"python":{"code":"import threading , queue\nclass Edge:\n def __init__(self,src,nbr,wt):\n self.src = src\n self.nbr = nbr\n self.wt=wt\n\n\ndef main():\n vtces = int(input())\n edges = int(input()) \n graph = {}\n for i in range(vtces):\n graph[i] = []\n \n for i in range(edges): \n lines = input().split(\" \")\n v1=int(lines[0])\n v2=int(lines[1])\n wt=int(lines[2])\n e1 = Edge(v1 ,v2 ,wt)\n e2 = Edge(v2 ,v1 ,wt)\n graph[e1.src].append(e1)\n graph[e2.src].append(e2) \n \n src = int(input()) \n t = int(input()) \n # Write your code here \n \n \nif __name__ == \"__main__\":\n main()"}},"points":10,"difficulty":"easy","sampleInput":"7\r\n8\r\n0 1 10\r\n1 2 10\r\n2 3 10\r\n0 3 10\r\n3 4 10\r\n4 5 10\r\n5 6 10\r\n4 6 10\r\n6\r\n3","sampleOutput":"4","questionVideo":"https://www.youtube.com/embed/3A1XJbRs_6A?end=161","hints":[],"associated":[{"id":"270bde7a-f0de-4ec3-8a89-72fe014da45f","name":"Which data structure is best suited for this problem ?","slug":"which-data-structure-is-best-suited-for-this-problem","type":4},{"id":"57241aa0-baa5-4c1c-8080-9dd0d7722635","name":"Which algorithm a single stack helps us to implement? (Spread Of Infection)","slug":"which-algorithm-a-single-stack-helps-us-to-implement-spread-of-infection","type":4},{"id":"5ad84dc8-cbe7-4447-932b-dd0c26736be1","name":"Which algorithm would you use if you have to reach all the neighbouring nodes first? (Spread Of Infection)","slug":"which-algorithm-would-you-use-if-you-have-to-reach-all-the-neighbouring-nodes-first-spread-of-infection","type":4},{"id":"d25926c4-c502-42eb-b3e7-ccfe3ed6ddea","name":"What is the rate of increase of spread of infection?","slug":"what-is-the-rate-of-increase-of-spread-of-infection","type":4}],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"02ab8fe3-cddd-43ad-b241-b8b1a2fcd52e","name":"Graphs For Beginners","slug":"graphs-for-beginners","type":0},{"id":"d28c9055-3c89-41dd-97a9-7b5ee4f56138","name":"Spread Of Infection","slug":"spread-of-infection","type":1}],"next":{"id":"51dac32b-6457-4a0d-b76a-0709e27b857f","name":"Spread of Infection","type":3,"slug":"spread-of-infection"},"prev":{"id":"a23a17fa-e27f-4dfd-ac4e-bdf6c0687482","name":"Is Graph Bipartite","type":3,"slug":"is-graph-bipartite"}}}
plane

Editor

Loading...

Spread Of Infection

easy

1. You are given a graph, representing people and their connectivity. 2. You are also given a src person (who got infected) and time t. 3. You are required to find how many people will get infected in time t, if the infection spreads to neighbors of infected person in 1 unit of time.

Constraints

None

Format

Input

Input has been managed for you

Output

count of people infected by time t

Example

Sample Input

7 8 0 1 10 1 2 10 2 3 10 0 3 10 3 4 10 4 5 10 5 6 10 4 6 10 6 3

Sample Output

4

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode