Java Programming Right now Im trying to find a proper way to store the input of

Question

Java Programming

Right now Im trying to find a proper way to store the input of the Scanner.in file this problem deals with minimum spanning trees using Prim's algorithm. The input file looks like this:

// Example Input

3

2 1

1 2 5

3 1

1 2 2

4 4

1 2 2

2 3 3

3 4 1

1 4 4

Okay, so the first line with 1 number indicates the number of cases (in this case its 3 cases). The lines with 2 numbers on it indicate the number of vertices and the number of edges. The lines with 3 numbers indicates the starting node #, the ending node # and the weight of the edge between the two nodes. I'm using Scanner input = new Scanner (System.in); to read the input.in file that matches as shown above. How would I write a java program that prints the sum total weight of the edges in the MST for each case (in this example 1 thru 3.... case 2 can't be solved so just print "No Solution")? I know that the second case isn't solvable too, also print if it can't be solved. I need it to work with the example input that I'm showing above.

My output I needs to look like this (printing out the sum of the edges):

Case 1 : 5

Case 2 : No solution

Case 3: 6

Explanation / Answer

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class MST {

    static int noOfCases;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        noOfCases = sc.nextInt();
        int[] weights = new int[noOfCases];
        for(int i=0; i<noOfCases;i++){
            List<Edge> edges = new ArrayList<Edge>();
            sc = new Scanner(System.in);
            String line = sc.nextLine();
            String components[] = line.split("\s+");
            int noOfVertices = Integer.parseInt(components[0]);
            int noOfEdges = Integer.parseInt(components[1]);
            for(int j=0; j<noOfEdges; j++){
                sc = new Scanner(System.in);
                line = sc.nextLine();
                components = line.split("\s+");
                int src = Integer.parseInt(components[0]);
                int dst = Integer.parseInt(components[1]);
                int weight = Integer.parseInt(components[2]);
                Edge e = new Edge(src, dst, weight);
                edges.add(e);
            }
            weights[i] = getWeightOfMST(edges,noOfVertices);
        }
        for(int i=0;i<noOfCases;i++){
            if(weights[i]<0){
                System.out.println("Case "+(i+1)+":No Solution");
            }else{
                System.out.println("Case "+(i+1)+":"+weights[i]);
            }
        }
    }

    static int    getWeightOfMST(List<Edge> edges, int noOfVertices){
        int sum = 0;
        Collections.sort(edges);
        List<Edge> mst = new ArrayList<Edge>();
        DisjointSet ds = new DisjointSet();
        ds.makeSet(noOfVertices);
        int index = 0;
        while(mst.size() != noOfVertices - 1){
            if(index >= edges.size()){
                return -1;
            }
            Edge nextEdge = edges.get(index++);
            int x = ds.find(nextEdge.src);
            int y = ds.find(nextEdge.dst);

            if(x != y){
                mst.add(nextEdge);
                ds.union(x, y);
            }
        }
        for(Edge e : mst){
            sum += e.weight;
        }
        return sum;
    }

}
-----------------------------------------------------------------------------------------------
import java.util.HashMap;
import java.util.Map;

public class DisjointSet {

    Map<Integer, Integer> parent = new HashMap<Integer, Integer>();

    public void makeSet(int n){
        for(int i=0; i<n; i++){
            parent.put(i+1, i+1);
        }
    }

    public int find(int k){
        if(parent.get(k) == k){
            return k;
        }
        return find(parent.get(k));
    }

    public void union(int a, int b){
        int x = find(a);
        int y = find(b);
        parent.put(x, y);
    }
}
--------------------------------------------------------------------------------------------------
public class Edge implements Comparable<Edge>{

    int src, dst, weight;

    public Edge(int src, int dst, int weight) {
        this.src = src;
        this.dst = dst;
        this.weight = weight;
    }

    @Override
    public int compareTo(Edge e) {
        return weight - e.weight;
    }
}

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.