{"id":"8a6db2d7-4a83-4a73-8f6c-784b2c4e351f","name":"Minimum Wire Required To Connect All Pcs","description":"1. You are given a graph and a source vertex. The vertices represent computers and the edges \r\n represent length of LAN wire required to connect them.\r\n2. You are required to find the minimum length of wire required to connect all PCs over a network. \r\n Print the output in terms of which all PCs need to be connected, and the length of wire between \r\n them.\r\n\r\nNote -> For output, check the sample output and question video.","inputFormat":"Input has been managed for you","outputFormat":"Check the sample output","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 int wt = 0;\n\n Edge(int src, int nbr, int wt)\n {\n this->src = src; \n this->nbr = nbr;\n this->wt = wt;\n }\n};\n\n \n\nint main() { \n \n int vtces;\n cin >> vtces;\n vector<vector<Edge>> graph(vtces, vector<Edge>());\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, w));\n graph[v].push_back(Edge(v, u, w));\n\n } \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 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\r\n}"},"python":{"code":"import threading \n\n\n\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 #Write your code here\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 40\r\n3 4 2\r\n4 5 3\r\n5 6 3\r\n4 6 8","sampleOutput":"[1-0@10]\r\n[2-1@10]\r\n[3-2@10]\r\n[4-3@2]\r\n[5-4@3]\r\n[6-5@3]","questionVideo":"https://www.youtube.com/embed/Vw-sktU1zmc?end=164","hints":[],"associated":[{"id":"57ba5284-0f4f-4541-889a-605686a70e14","name":"Kruskal's algorithm uses which data structure? (minimum_wire_required_to_connect_all_pieces)","slug":"kruskal-s-algorithm-uses-which-data-structure-minimum-wire-required-to-connect-all-pieces","type":4},{"id":"b34a61be-7ef3-4dc4-b1bb-853a64995497","name":"What is the Time Complexity of the Prim's algorithm? (minimum_wire_required_to_connect_all_pieces)","slug":"what-is-the-time-complexity-of-the-prim-s-algorithm-minimum-wire-required-to-connect-all-pieces","type":4},{"id":"e07c3eca-33f2-4b30-a295-86b8e9ffd01a","name":"An MST of n nodes will consist of _____ edges. (minimum_wire_required_to_connect_all_pieces)","slug":"an-mst-of-n-nodes-will-consist-of-edges-minimum-wire-required-to-connect-all-pieces","type":4},{"id":"f791a331-739b-465c-807b-549b24742747","name":"Minimum Spanning Tree can consist of cycles.' Is this statement true? (minimum_wire_required_to_connect_all_pieces)","slug":"minimum-spanning-tree-can-consist-of-cycles-is-this-statement-true-minimum-wire-required-to-connect-all-pieces","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":"c251ec5e-94ae-40a2-bc75-bb3f12f8cfbd","name":"Minimum Wire Required To Connect All Pcs","slug":"minimum-wire-required-to-connect-all-pcs","type":1}],"next":{"id":"fbeaf6b1-afec-46d8-9410-38ad6bc5b0c1","name":"MIN WIRE REQUIRED TO CONNECT ALL PCS","type":3,"slug":"min-wire-required-to-connect-all-pcs"},"prev":{"id":"920b9140-9643-4c4f-889e-6ad352029d24","name":"Shortest Path in weights","type":3,"slug":"shortest-path-in-weights"}}}

Minimum Wire Required To Connect All Pcs

1. You are given a graph and a source vertex. The vertices represent computers and the edges represent length of LAN wire required to connect them. 2. You are required to find the minimum length of wire required to connect all PCs over a network. Print the output in terms of which all PCs need to be connected, and the length of wire between them. Note -> For output, check the sample output and question video.

{"id":"8a6db2d7-4a83-4a73-8f6c-784b2c4e351f","name":"Minimum Wire Required To Connect All Pcs","description":"1. You are given a graph and a source vertex. The vertices represent computers and the edges \r\n represent length of LAN wire required to connect them.\r\n2. You are required to find the minimum length of wire required to connect all PCs over a network. \r\n Print the output in terms of which all PCs need to be connected, and the length of wire between \r\n them.\r\n\r\nNote -> For output, check the sample output and question video.","inputFormat":"Input has been managed for you","outputFormat":"Check the sample output","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 int wt = 0;\n\n Edge(int src, int nbr, int wt)\n {\n this->src = src; \n this->nbr = nbr;\n this->wt = wt;\n }\n};\n\n \n\nint main() { \n \n int vtces;\n cin >> vtces;\n vector<vector<Edge>> graph(vtces, vector<Edge>());\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, w));\n graph[v].push_back(Edge(v, u, w));\n\n } \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 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\r\n}"},"python":{"code":"import threading \n\n\n\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 #Write your code here\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 40\r\n3 4 2\r\n4 5 3\r\n5 6 3\r\n4 6 8","sampleOutput":"[1-0@10]\r\n[2-1@10]\r\n[3-2@10]\r\n[4-3@2]\r\n[5-4@3]\r\n[6-5@3]","questionVideo":"https://www.youtube.com/embed/Vw-sktU1zmc?end=164","hints":[],"associated":[{"id":"57ba5284-0f4f-4541-889a-605686a70e14","name":"Kruskal's algorithm uses which data structure? (minimum_wire_required_to_connect_all_pieces)","slug":"kruskal-s-algorithm-uses-which-data-structure-minimum-wire-required-to-connect-all-pieces","type":4},{"id":"b34a61be-7ef3-4dc4-b1bb-853a64995497","name":"What is the Time Complexity of the Prim's algorithm? (minimum_wire_required_to_connect_all_pieces)","slug":"what-is-the-time-complexity-of-the-prim-s-algorithm-minimum-wire-required-to-connect-all-pieces","type":4},{"id":"e07c3eca-33f2-4b30-a295-86b8e9ffd01a","name":"An MST of n nodes will consist of _____ edges. (minimum_wire_required_to_connect_all_pieces)","slug":"an-mst-of-n-nodes-will-consist-of-edges-minimum-wire-required-to-connect-all-pieces","type":4},{"id":"f791a331-739b-465c-807b-549b24742747","name":"Minimum Spanning Tree can consist of cycles.' Is this statement true? (minimum_wire_required_to_connect_all_pieces)","slug":"minimum-spanning-tree-can-consist-of-cycles-is-this-statement-true-minimum-wire-required-to-connect-all-pieces","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":"c251ec5e-94ae-40a2-bc75-bb3f12f8cfbd","name":"Minimum Wire Required To Connect All Pcs","slug":"minimum-wire-required-to-connect-all-pcs","type":1}],"next":{"id":"fbeaf6b1-afec-46d8-9410-38ad6bc5b0c1","name":"MIN WIRE REQUIRED TO CONNECT ALL PCS","type":3,"slug":"min-wire-required-to-connect-all-pcs"},"prev":{"id":"920b9140-9643-4c4f-889e-6ad352029d24","name":"Shortest Path in weights","type":3,"slug":"shortest-path-in-weights"}}}
plane

Editor

Loading...

Minimum Wire Required To Connect All Pcs

easy

1. You are given a graph and a source vertex. The vertices represent computers and the edges represent length of LAN wire required to connect them. 2. You are required to find the minimum length of wire required to connect all PCs over a network. Print the output in terms of which all PCs need to be connected, and the length of wire between them. Note -> For output, check the sample output and question video.

Constraints

None

Format

Input

Input has been managed for you

Output

Check the sample output

Example

Sample Input

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

Sample Output

[1-0@10] [2-1@10] [3-2@10] [4-3@2] [5-4@3] [6-5@3]

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode