{"id":"f73742db-2d8e-4b81-b5cd-d783c5d1fca7","name":"Get Connected Components Of A Graph","description":"<p>1. You are given a graph. 2. You are required to find and print all connected components of the graph.</p>","inputFormat":"Input has been managed for you","outputFormat":"Check the sample output","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 \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 \n vector<vector<int>> comps;\n \n // write your code here\n \n \n cout<<\"[\";\n for(int i = 0 ; i<comps.size() ; i++){\n cout<<\"[\";\n for(int j = 0 ; j<comps[i].size() ; j++){\n if(j!=comps[i].size()-1)\n cout<<comps[i][j]<<\", \";\n else\n cout<<comps[i][j];\n\n }\n cout<<\"]\";\n if(i!=comps.size()-1)cout<<\", \";\n }\n cout<<\"]\";\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 ArrayList<ArrayList<Integer>> comps = new ArrayList<>();\r\n \r\n // write your code here\r\n\r\n System.out.println(comps);\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 e1 = Edge(int(values[0]), int(values[1]), int(values[2]))\n e2 = Edge(int(values[1]), int(values[0]), int(values[2]))\n graph[e1.src].append(e1)\n graph[e2.src].append(e2)\n\n comps = []\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":"[[0, 1], [2, 3], [4, 5, 6]]","questionVideo":"https://www.youtube.com/embed/8UBwFE8H4Mc?start=0&end=86","hints":[],"associated":[{"id":"2564dd2a-7794-4e92-8d70-9db9b29f2f9f","name":"which will be the best approach to find the connected components of the graph? (get connected components of the graph)","slug":"which-will-be-the-best-approach-to-find-the-connected-components-of-the-graph-get-connected-components-of-the-graph","type":4},{"id":"5667a895-d25f-40e6-826c-9e29f9c86f52","name":"0 1 10 2 3 10 4 5 10 5 6 10 4 6 10 what will be the connected components of the above graph? (get connected components of the graph)","slug":"0-1-10-2-3-10-4-5-10-5-6-10-4-6-10-what-will-be-the-connected-components-of-the-above-graph-get-connected-components-of-the-graph","type":4},{"id":"e08e99f7-ee28-4ff7-bc10-a479b0f25858","name":"what is the Space complexity of the traversal of the graph ? (get connected components of the graph)","slug":"what-is-the-space-complexity-of-the-traversal-of-the-graph-get-connected-components-of-the-graph","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":"97e08da3-bd88-4693-890d-3c7b0582c169","name":"Get Connected Components Of A Graph","slug":"get-connected-components-of-a-graph","type":1}],"next":{"id":"3365702c-1e91-4930-9893-519b413eed1d","name":"Get connected components of a graph","type":3,"slug":"get-connected-components-of-a-graph"},"prev":{"id":"66628ba5-69be-4651-aac0-07a6a5ef5793","name":"Multisolver - Smallest, Longest, Ceil, Floor, Kth Largest Path","type":3,"slug":"multisolver-smallest-longest-ceil-floor-kth-largest-path"}}}<p>1. You are given a graph. 2. You are required to find and print all connected components of the graph.</p>
{"id":"f73742db-2d8e-4b81-b5cd-d783c5d1fca7","name":"Get Connected Components Of A Graph","description":"<p>1. You are given a graph. 2. You are required to find and print all connected components of the graph.</p>","inputFormat":"Input has been managed for you","outputFormat":"Check the sample output","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 \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 \n vector<vector<int>> comps;\n \n // write your code here\n \n \n cout<<\"[\";\n for(int i = 0 ; i<comps.size() ; i++){\n cout<<\"[\";\n for(int j = 0 ; j<comps[i].size() ; j++){\n if(j!=comps[i].size()-1)\n cout<<comps[i][j]<<\", \";\n else\n cout<<comps[i][j];\n\n }\n cout<<\"]\";\n if(i!=comps.size()-1)cout<<\", \";\n }\n cout<<\"]\";\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 ArrayList<ArrayList<Integer>> comps = new ArrayList<>();\r\n \r\n // write your code here\r\n\r\n System.out.println(comps);\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 e1 = Edge(int(values[0]), int(values[1]), int(values[2]))\n e2 = Edge(int(values[1]), int(values[0]), int(values[2]))\n graph[e1.src].append(e1)\n graph[e2.src].append(e2)\n\n comps = []\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":"[[0, 1], [2, 3], [4, 5, 6]]","questionVideo":"https://www.youtube.com/embed/8UBwFE8H4Mc?start=0&end=86","hints":[],"associated":[{"id":"2564dd2a-7794-4e92-8d70-9db9b29f2f9f","name":"which will be the best approach to find the connected components of the graph? (get connected components of the graph)","slug":"which-will-be-the-best-approach-to-find-the-connected-components-of-the-graph-get-connected-components-of-the-graph","type":4},{"id":"5667a895-d25f-40e6-826c-9e29f9c86f52","name":"0 1 10 2 3 10 4 5 10 5 6 10 4 6 10 what will be the connected components of the above graph? (get connected components of the graph)","slug":"0-1-10-2-3-10-4-5-10-5-6-10-4-6-10-what-will-be-the-connected-components-of-the-above-graph-get-connected-components-of-the-graph","type":4},{"id":"e08e99f7-ee28-4ff7-bc10-a479b0f25858","name":"what is the Space complexity of the traversal of the graph ? (get connected components of the graph)","slug":"what-is-the-space-complexity-of-the-traversal-of-the-graph-get-connected-components-of-the-graph","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":"97e08da3-bd88-4693-890d-3c7b0582c169","name":"Get Connected Components Of A Graph","slug":"get-connected-components-of-a-graph","type":1}],"next":{"id":"3365702c-1e91-4930-9893-519b413eed1d","name":"Get connected components of a graph","type":3,"slug":"get-connected-components-of-a-graph"},"prev":{"id":"66628ba5-69be-4651-aac0-07a6a5ef5793","name":"Multisolver - Smallest, Longest, Ceil, Floor, Kth Largest Path","type":3,"slug":"multisolver-smallest-longest-ceil-floor-kth-largest-path"}}}
Editor
Discussions
Show Discussion
Related Resources
