{"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"}}}

Get Connected Components Of A Graph

<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"}}}
plane

Editor


Loading...

Get Connected Components Of A Graph

easy

1. You are given a graph. 2. You are required to find and print all connected components of the graph.

Constraints

None

Format

Input

Input has been managed for you

Output

Check the sample output

Example

Sample Input

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

Sample Output

[[0, 1], [2, 3], [4, 5, 6]]

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode