{"id":"410793d3-7b54-4786-9b85-a36ae30c7298","name":"Has Path?","description":"1. You are given a graph, a src vertex and a destination vertex.\r\n2. You are required to find if a path exists between src and dest. If it does, print true \r\n otherwise print false.","inputFormat":"Input has been managed for you","outputFormat":"true if path exists, false otherwise","constraints":"None","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\n class Edge {\n public:\n int src;\n int nbr;\n int wt;\n\n Edge(int src, int nbr, int wt){\n this->src = src;\n this->nbr = nbr;\n this->wt = wt;\n }\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 int wt;\r\n\r\n Edge(int src, int nbr, int wt){\r\n this.src = src;\r\n this.nbr = nbr;\r\n this.wt = wt;\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 int wt = Integer.parseInt(parts[2]);\r\n graph[v1].add(new Edge(v1, v2, wt));\r\n graph[v2].add(new Edge(v2, v1, wt));\r\n }\r\n\r\n int src = Integer.parseInt(br.readLine());\r\n int dest = Integer.parseInt(br.readLine());\r\n\r\n // write your code here\r\n }\r\n\r\n}"},"python":{"code":"class 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 values = input().split(\" \")\n v1 = int(values[0])\n v2 = int(values[1])\n wt = int(values[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 dest = 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\n0\r\n6","sampleOutput":"true","questionVideo":"https://www.youtube.com/embed/mlnnJd9k7oE?start=0&end=21","hints":[],"associated":[{"id":"18ef3f84-bb6d-48e0-b6cf-65c994ba644c","name":"What is the space complexity of \"Has Path\" approach?","slug":"what-is-the-space-complexity-of-has-path-approach","type":4},{"id":"43f3d4cf-5646-4554-8cb4-b0ec43d4a975","name":"What is the time complexity of \"Has Path\" approach?","slug":"what-is-the-time-complexity-of-has-path-approach","type":4},{"id":"b8d0d1fd-3f6a-4541-8e70-374b672e8341","name":"What will be the base case for \"Has Path\" question?","slug":"what-will-be-the-base-case-for-has-path-question","type":4},{"id":"c18a3795-d6e2-4255-9973-607b3905e35e","name":"Which of the following methods you can use to solve \"Has Path problem?","slug":"which-of-the-following-methods-you-can-use-to-solve-has-path-problem","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":"e388e079-e3af-49cf-89bb-b5919828738b","name":"Has Path?","slug":"has-path","type":1}],"next":{"id":"88f3e4e7-65b2-40e4-9c64-f6242756faf3","name":"Has Path.","type":3,"slug":"has-path"},"prev":{"id":"00a38f21-e4ac-43bd-8792-91c45967dc2c","name":"Introduction To Graphs and its Representation","type":3,"slug":"introduction-to-graphs-and-its-representation"}}}

Has Path?

1. You are given a graph, a src vertex and a destination vertex. 2. You are required to find if a path exists between src and dest. If it does, print true otherwise print false.

{"id":"410793d3-7b54-4786-9b85-a36ae30c7298","name":"Has Path?","description":"1. You are given a graph, a src vertex and a destination vertex.\r\n2. You are required to find if a path exists between src and dest. If it does, print true \r\n otherwise print false.","inputFormat":"Input has been managed for you","outputFormat":"true if path exists, false otherwise","constraints":"None","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\n class Edge {\n public:\n int src;\n int nbr;\n int wt;\n\n Edge(int src, int nbr, int wt){\n this->src = src;\n this->nbr = nbr;\n this->wt = wt;\n }\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 int wt;\r\n\r\n Edge(int src, int nbr, int wt){\r\n this.src = src;\r\n this.nbr = nbr;\r\n this.wt = wt;\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 int wt = Integer.parseInt(parts[2]);\r\n graph[v1].add(new Edge(v1, v2, wt));\r\n graph[v2].add(new Edge(v2, v1, wt));\r\n }\r\n\r\n int src = Integer.parseInt(br.readLine());\r\n int dest = Integer.parseInt(br.readLine());\r\n\r\n // write your code here\r\n }\r\n\r\n}"},"python":{"code":"class 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 values = input().split(\" \")\n v1 = int(values[0])\n v2 = int(values[1])\n wt = int(values[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 dest = 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\n0\r\n6","sampleOutput":"true","questionVideo":"https://www.youtube.com/embed/mlnnJd9k7oE?start=0&end=21","hints":[],"associated":[{"id":"18ef3f84-bb6d-48e0-b6cf-65c994ba644c","name":"What is the space complexity of \"Has Path\" approach?","slug":"what-is-the-space-complexity-of-has-path-approach","type":4},{"id":"43f3d4cf-5646-4554-8cb4-b0ec43d4a975","name":"What is the time complexity of \"Has Path\" approach?","slug":"what-is-the-time-complexity-of-has-path-approach","type":4},{"id":"b8d0d1fd-3f6a-4541-8e70-374b672e8341","name":"What will be the base case for \"Has Path\" question?","slug":"what-will-be-the-base-case-for-has-path-question","type":4},{"id":"c18a3795-d6e2-4255-9973-607b3905e35e","name":"Which of the following methods you can use to solve \"Has Path problem?","slug":"which-of-the-following-methods-you-can-use-to-solve-has-path-problem","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":"e388e079-e3af-49cf-89bb-b5919828738b","name":"Has Path?","slug":"has-path","type":1}],"next":{"id":"88f3e4e7-65b2-40e4-9c64-f6242756faf3","name":"Has Path.","type":3,"slug":"has-path"},"prev":{"id":"00a38f21-e4ac-43bd-8792-91c45967dc2c","name":"Introduction To Graphs and its Representation","type":3,"slug":"introduction-to-graphs-and-its-representation"}}}
plane

Editor


Loading...

Has Path?

easy

1. You are given a graph, a src vertex and a destination vertex. 2. You are required to find if a path exists between src and dest. If it does, print true otherwise print false.

Constraints

None

Format

Input

Input has been managed for you

Output

true if path exists, false otherwise

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 0 6

Sample Output

true

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode