kruskal

mail@pastecode.io avatar
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) {
        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();
    }
}