kruskal
unknown
plain_text
3 years ago
2.6 kB
6
Indexable
import java.io.*; import java.util.*; class UnionFind { int n; int[] parent; UnionFind(int n) { this.n = n; parent = new int[n]; // Init parent of a vertex to be the vertex itself for (int i = 0; i < n; i++) { parent[i] = i; } } public void unite(int i, int j) { if (parent[i] != i) { unite(parent[i], j); } parent[i] = j; } public int findParent(int i) { if (parent[i] == i) { return i; } return findParent(parent[i]); } public boolean isConnected(int i1, int i2) { // 2 vertices is connected if they has the same parent return findParent(i1) == findParent(i2); } } class Edge implements Comparable<Edge> { int v1; int v2; int weight; Edge(int v1, int v2, int weight) { this.v1 = v1; this.v2 = v2; this.weight = weight; } public int compareTo(Edge b) { return (b.weight < this.weight) ? 1 : -1; } } class Graph { public List<Edge> edges = new ArrayList<>(); public void addEdge(int v1, int v2, int w) { edges.add(new Edge(v1, v2, w)); } public int kruskal(int n) { PriorityQueue<Edge> queue = new PriorityQueue<>(); UnionFind uf = new UnionFind(n); int total = 0; // total weight of the MST for (Edge edge : edges) { queue.add(edge); } while (!queue.isEmpty()) { Edge e = queue.poll(); int v1 = e.v1; int v2 = e.v2; // Check for cycle if (!uf.isConnected(v1, v2)) { // No cycle uf.unite(v1, v2); // set the two vertices to the same subset total += e.weight; } } return total; } } public class Solution { public static void main(String[] args) throws IOException { Graph g = new Graph(); Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); for (int i = 0; i < m; i++) { int v1 = sc.nextInt() - 1; int v2 = sc.nextInt() - 1; int w = sc.nextInt(); if (v1 > v2) { g.addEdge(v2, v1, w); } else { g.addEdge(v1, v2, w); } } System.out.println(g.kruskal(n)); sc.close(); } }
Editor is loading...