# kruskal

unknown
plain_text
2 years ago
2.6 kB
3
Indexable
Never
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) {
}

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

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;
}

}

}
}

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) {