{"id":"916e77cd-2458-4e95-b504-bca36d82741a","name":"Is Graph Connected","description":"1. You are given a graph.\r\n2. You are required to find and print if the graph is connected (there is a path from \r\n every vertex to every other).","inputFormat":"Input has been managed for you","outputFormat":"true if the graph is connected, 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 };\n \n int main(){\n int vtces;\n cin>>vtces;\n vector<Edge>graph[vtces];\n\n int edges;\n cin>>edges;\n for(int i = 0; i < edges; i++){\n int v1 ;\n int v2 ;\n int wt ;\n cin>>v1>>v2>>wt;\n graph[v1].push_back( Edge(v1, v2, wt));\n graph[v2].push_back( Edge(v2, v1, wt));\n }\n\n int src;\n cin>>src;\n int dest;\n cin>>dest;\n // write your code here\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\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 // write your code here\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\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 vis = [False]*vtces\n \n # write your code here\n \n \nif __name__ == \"__main__\":\n main()"}},"points":10,"difficulty":"easy","sampleInput":"7\r\n5\r\n0 1 10\r\n2 3 10\r\n4 5 10\r\n5 6 10\r\n4 6 10","sampleOutput":"false","questionVideo":"https://www.youtube.com/embed/dRqO3s14_2s?start=0&end=64","hints":[],"associated":[{"id":"05ea648f-e126-4cf8-9c2d-decbc549cba9","name":"What is the number of edges present in a complete graph having n vertices? (Is Graph Connected)","slug":"what-is-the-number-of-edges-present-in-a-complete-graph-having-n-vertices-is-graph-connected","type":4},{"id":"56f7cd18-26fa-4b47-b3cc-8bde65fc5ffe","name":"Which graph is called a connected graph (Is Graph Connected)","slug":"which-graph-is-called-a-connected-graph-is-graph-connected","type":4},{"id":"a955381a-199d-49fb-a62a-476d81c6015f","name":"The most efficient algorithm for finding the number of connected components in an undirected graph on n vertices and m edges has time complexity.(Is Graph Connected)","slug":"the-most-efficient-algorithm-for-finding-the-number-of-connected-components-in-an-undirected-graph-on-n-vertices-and-m-edges-has-time-complexity-is-graph-connected","type":4},{"id":"fcfd97fa-5c02-4caf-ae13-066008a72333","name":"Why we use visited array in graph ? (Is Graph Connected)","slug":"why-we-use-visited-array-in-graph-is-graph-connected","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":"2e57210c-bf9e-48ac-bdb9-95b0f5d775f5","name":"Is Graph Connected","slug":"is-graph-connected","type":1}],"next":{"id":"777bb2a2-0a00-45bd-a2d0-c2f08b480cfd","name":"IS GRAPH CONNECTED","type":3,"slug":"is-graph-connected"},"prev":{"id":"3365702c-1e91-4930-9893-519b413eed1d","name":"Get connected components of a graph","type":3,"slug":"get-connected-components-of-a-graph"}}}

Is Graph Connected

1. You are given a graph. 2. You are required to find and print if the graph is connected (there is a path from every vertex to every other).

{"id":"916e77cd-2458-4e95-b504-bca36d82741a","name":"Is Graph Connected","description":"1. You are given a graph.\r\n2. You are required to find and print if the graph is connected (there is a path from \r\n every vertex to every other).","inputFormat":"Input has been managed for you","outputFormat":"true if the graph is connected, 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 };\n \n int main(){\n int vtces;\n cin>>vtces;\n vector<Edge>graph[vtces];\n\n int edges;\n cin>>edges;\n for(int i = 0; i < edges; i++){\n int v1 ;\n int v2 ;\n int wt ;\n cin>>v1>>v2>>wt;\n graph[v1].push_back( Edge(v1, v2, wt));\n graph[v2].push_back( Edge(v2, v1, wt));\n }\n\n int src;\n cin>>src;\n int dest;\n cin>>dest;\n // write your code here\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\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 // write your code here\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\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 vis = [False]*vtces\n \n # write your code here\n \n \nif __name__ == \"__main__\":\n main()"}},"points":10,"difficulty":"easy","sampleInput":"7\r\n5\r\n0 1 10\r\n2 3 10\r\n4 5 10\r\n5 6 10\r\n4 6 10","sampleOutput":"false","questionVideo":"https://www.youtube.com/embed/dRqO3s14_2s?start=0&end=64","hints":[],"associated":[{"id":"05ea648f-e126-4cf8-9c2d-decbc549cba9","name":"What is the number of edges present in a complete graph having n vertices? (Is Graph Connected)","slug":"what-is-the-number-of-edges-present-in-a-complete-graph-having-n-vertices-is-graph-connected","type":4},{"id":"56f7cd18-26fa-4b47-b3cc-8bde65fc5ffe","name":"Which graph is called a connected graph (Is Graph Connected)","slug":"which-graph-is-called-a-connected-graph-is-graph-connected","type":4},{"id":"a955381a-199d-49fb-a62a-476d81c6015f","name":"The most efficient algorithm for finding the number of connected components in an undirected graph on n vertices and m edges has time complexity.(Is Graph Connected)","slug":"the-most-efficient-algorithm-for-finding-the-number-of-connected-components-in-an-undirected-graph-on-n-vertices-and-m-edges-has-time-complexity-is-graph-connected","type":4},{"id":"fcfd97fa-5c02-4caf-ae13-066008a72333","name":"Why we use visited array in graph ? (Is Graph Connected)","slug":"why-we-use-visited-array-in-graph-is-graph-connected","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":"2e57210c-bf9e-48ac-bdb9-95b0f5d775f5","name":"Is Graph Connected","slug":"is-graph-connected","type":1}],"next":{"id":"777bb2a2-0a00-45bd-a2d0-c2f08b480cfd","name":"IS GRAPH CONNECTED","type":3,"slug":"is-graph-connected"},"prev":{"id":"3365702c-1e91-4930-9893-519b413eed1d","name":"Get connected components of a graph","type":3,"slug":"get-connected-components-of-a-graph"}}}
plane

Editor


Loading...

Is Graph Connected

easy

1. You are given a graph. 2. You are required to find and print if the graph is connected (there is a path from every vertex to every other).

Constraints

None

Format

Input

Input has been managed for you

Output

true if the graph is connected, false otherwise

Example

Sample Input

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

Sample Output

false

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode