Java Kruskal

Kruskal裸题 直接套模板

（本来想再写一个Prim.... 太难了）

    public int miniSpanningTree (int n, int m, int[][] cost) {
        // write code here
        int[] father = new int[n+1];
        for(int i=0;i<father.length;++i){
            father[i] = i;
        }

        PriorityQueue<Node> queue = new PriorityQueue<>((a,b)->a.cost-b.cost);
        for(int [] c: cost){
            queue.add(new Node(c[2],c[1],c[0]));
        }

        int ans = 0;
        while(!queue.isEmpty()){
            Node cur = queue.poll();
            if(find(father,cur.start) != find(father,cur.end)){
                ans += cur.cost;
                union(father,cur.start,cur.end);
            }
        }
        return ans;

    }

    static class Node{
        int cost;
        int start;
        int end;
        public Node(int c,int s , int e){
            this.start=s;
            this.end = e;
            this.cost = c;
        }
    }

    public int find(int[] f,int a){
        if(f[a] ==a){
            return a;
        }
        return f[a]=find(f,f[a]);
    }

    public void union(int[] f, int a ,int b){
        int fa = find(f,a);
        int fb = find(f,b);
        f[fa]=fb;
    }