{"id":"70c4eb84-b7b0-4dde-ad98-97168a509639","name":"Kruskal Algorithm","description":"There are n vertices and there are edges in between some of the vertices. Find the sum of edge weight of minimum spanning tree.","inputFormat":"First line contains number of vertices.\r\nSecond line contains number of edges.\r\nEach of next E lines contain 3 number u and v and c denoting an edge between u and v with weight c.","outputFormat":"print the sum of edge weight of MST.","constraints":"1&lt;= n &lt;= 1000\r\n1&lt;= e &lt;= n*(n-1)/2","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\nint main(){\n int v,e;\n cin>>v>>e;\n \n vector<vector<int>>pipes(e,vector<int>(3));\n \n for(int i=0;i<e;i++){\n for(int j=0;j<3;j++){\n cin>>pipes[i][j];\n }\n }\n cout<<minCostToSupplyWater(v,pipes);\n }"},"java":{"code":"import java.util.*;\nimport java.io.*;\n\npublic class Main {\n\n public static void main(String[] args) throws Exception {\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\n int v = Integer.parseInt(br.readLine());\n int e = Integer.parseInt(br.readLine());\n\n int[][] edges = new int[e][3];\n for (int i = 0; i < e; i++) {\n String[] st = br.readLine().split(\" \");\n edges[i][0] = Integer.parseInt(st[0]);\n edges[i][1] = Integer.parseInt(st[1]);\n edges[i][2] = Integer.parseInt(st[2]);\n }\n\n System.out.println(minCostToSupplyWater(v, edges));\n }\n\n static int[] parent;\n static int[] rank;\n\n public static class Pair implements Comparable<Pair> {\n int u;\n int v;\n int wt;\n\n Pair(int u, int v, int wt) {\n this.u = u;\n this.v = v;\n this.wt = wt;\n }\n\n @Override\n public int compareTo(Pair o) {\n return this.wt - o.wt;\n }\n }\n\n public static int minCostToSupplyWater(int n, int[][] pipes) {\n\n\n }\n}\n"},"python":{"code":""}},"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":"38\r\n","questionVideo":"","hints":[],"associated":[],"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":"7e07fddf-83bd-421e-848f-118f1f29541c","name":"Graphs For Intermediate","slug":"graphs-for-intermediate-493","type":0},{"id":"1914183b-5709-4db1-94ca-01987c7601e2","name":"Kruskal Algorithm","slug":"kruskal-algorithm","type":1}],"next":{"id":"6bbd9a65-3c2f-4685-b580-5ca6406495e7","name":"Kruskal Algorithm MCQ","type":0,"slug":"kruskal-algorithm-mcq"},"prev":{"id":"1db07064-9767-46e0-b9ff-6ca383620bc5","name":"OPTIMIZE WATER DISTRIBUTION","type":3,"slug":"optimize-water-distribution"}}}

Kruskal Algorithm

There are n vertices and there are edges in between some of the vertices. Find the sum of edge weight of minimum spanning tree.

{"id":"70c4eb84-b7b0-4dde-ad98-97168a509639","name":"Kruskal Algorithm","description":"There are n vertices and there are edges in between some of the vertices. Find the sum of edge weight of minimum spanning tree.","inputFormat":"First line contains number of vertices.\r\nSecond line contains number of edges.\r\nEach of next E lines contain 3 number u and v and c denoting an edge between u and v with weight c.","outputFormat":"print the sum of edge weight of MST.","constraints":"1&lt;= n &lt;= 1000\r\n1&lt;= e &lt;= n*(n-1)/2","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\nint main(){\n int v,e;\n cin>>v>>e;\n \n vector<vector<int>>pipes(e,vector<int>(3));\n \n for(int i=0;i<e;i++){\n for(int j=0;j<3;j++){\n cin>>pipes[i][j];\n }\n }\n cout<<minCostToSupplyWater(v,pipes);\n }"},"java":{"code":"import java.util.*;\nimport java.io.*;\n\npublic class Main {\n\n public static void main(String[] args) throws Exception {\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\n int v = Integer.parseInt(br.readLine());\n int e = Integer.parseInt(br.readLine());\n\n int[][] edges = new int[e][3];\n for (int i = 0; i < e; i++) {\n String[] st = br.readLine().split(\" \");\n edges[i][0] = Integer.parseInt(st[0]);\n edges[i][1] = Integer.parseInt(st[1]);\n edges[i][2] = Integer.parseInt(st[2]);\n }\n\n System.out.println(minCostToSupplyWater(v, edges));\n }\n\n static int[] parent;\n static int[] rank;\n\n public static class Pair implements Comparable<Pair> {\n int u;\n int v;\n int wt;\n\n Pair(int u, int v, int wt) {\n this.u = u;\n this.v = v;\n this.wt = wt;\n }\n\n @Override\n public int compareTo(Pair o) {\n return this.wt - o.wt;\n }\n }\n\n public static int minCostToSupplyWater(int n, int[][] pipes) {\n\n\n }\n}\n"},"python":{"code":""}},"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":"38\r\n","questionVideo":"","hints":[],"associated":[],"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":"7e07fddf-83bd-421e-848f-118f1f29541c","name":"Graphs For Intermediate","slug":"graphs-for-intermediate-493","type":0},{"id":"1914183b-5709-4db1-94ca-01987c7601e2","name":"Kruskal Algorithm","slug":"kruskal-algorithm","type":1}],"next":{"id":"6bbd9a65-3c2f-4685-b580-5ca6406495e7","name":"Kruskal Algorithm MCQ","type":0,"slug":"kruskal-algorithm-mcq"},"prev":{"id":"1db07064-9767-46e0-b9ff-6ca383620bc5","name":"OPTIMIZE WATER DISTRIBUTION","type":3,"slug":"optimize-water-distribution"}}}
plane

Editor

Loading...

Kruskal Algorithm

easy

There are n vertices and there are edges in between some of the vertices. Find the sum of edge weight of minimum spanning tree.

Constraints

1<= n <= 1000 1<= e <= n*(n-1)/2

Format

Input

First line contains number of vertices. Second line contains number of edges. Each of next E lines contain 3 number u and v and c denoting an edge between u and v with weight c.

Output

print the sum of edge weight of MST.

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

38

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode