// Java program for Kruskal's algorithm to find Minimum 
// Spanning Tree of a given connected, undirected and 
// weighted graph 
import java.util.*; 
import java.lang.*; 
import java.io.*; 

class Graph 
{ 
	// A class to represent a graph edge 
	class Edge implements Comparable<Edge> 
	{ 
		int src, dest, weight; 

		// Comparator function used for sorting edges 
		// based on their weight 
		public int compareTo(Edge compareEdge) 
		{ 
			return this.weight-compareEdge.weight; 
		} 
	}; 

	// A class to represent a subset for union-find 
	class subset 
	{ 
		int parent, rank; 
	}; 

	int V, E; // V-> no. of vertices & E->no.of edges 
	Edge edge[]; // collection of all edges 

	// Creates a graph with V vertices and E edges 
	Graph(int v, int e) 
	{ 
		V = v; 
		E = e; 
		edge = new Edge[E]; 
		for (int i=0; i<e; ++i) 
			edge[i] = new Edge(); 
	} 

	// A utility function to find set of an element i 
	// (uses path compression technique) 
	int find(subset subsets[], int i) 
	{ 
		// find root and make root as parent of i (path compression) 
		if (subsets[i].parent != i) 
			subsets[i].parent = find(subsets, subsets[i].parent); 

		return subsets[i].parent; 
	} 

	// A function that does union of two sets of x and y 
	// (uses union by rank) 
	void Union(subset subsets[], int x, int y) 
	{ 
		int xroot = find(subsets, x); 
		int yroot = find(subsets, y); 

		// Attach smaller rank tree under root of high rank tree 
		// (Union by Rank) 
		if (subsets[xroot].rank < subsets[yroot].rank) 
			subsets[xroot].parent = yroot; 
		else if (subsets[xroot].rank > subsets[yroot].rank) 
			subsets[yroot].parent = xroot; 

		// If ranks are same, then make one as root and increment 
		// its rank by one 
		else
		{ 
			subsets[yroot].parent = xroot; 
			subsets[xroot].rank++; 
		} 
	} 

	// The main function to construct MST using Kruskal's algorithm 
	void KruskalMST() 
	{ 
		Edge result[] = new Edge[V]; // Tnis will store the resultant MST 
		int e = 0; // An index variable, used for result[] 
		int i = 0; // An index variable, used for sorted edges 
		for (i=0; i<V; ++i) 
			result[i] = new Edge(); 

		// Step 1: Sort all the edges in non-decreasing order of their 
		// weight. If we are not allowed to change the given graph, we 
		// can create a copy of array of edges 
		Arrays.sort(edge); 

		// Allocate memory for creating V ssubsets 
		subset subsets[] = new subset[V]; 
		for(i=0; i<V; ++i) 
			subsets[i]=new subset(); 

		// Create V subsets with single elements 
		for (int v = 0; v < V; ++v) 
		{ 
			subsets[v].parent = v; 
			subsets[v].rank = 0; 
		} 

		i = 0; // Index used to pick next edge 

		// Number of edges to be taken is equal to V-1 
		while (e < V - 1) 
		{ 
			// Step 2: Pick the smallest edge. And increment 
			// the index for next iteration 
			Edge next_edge = new Edge(); 
			next_edge = edge[i++]; 

			int x = find(subsets, next_edge.src); 
			int y = find(subsets, next_edge.dest); 

			// If including this edge does't cause cycle, 
			// include it in result and increment the index 
			// of result for next edge 
			if (x != y) 
			{ 
				result[e++] = next_edge; 
				Union(subsets, x, y); 
			} 
			// Else discard the next_edge 
		} 

		// print the contents of result[] to display 
		// the built MST 
		System.out.println("Following are the edges in " + 
									"the constructed MST"); 
		for (i = 0; i < e; ++i) 
			System.out.println(result[i].src+" -- " + 
				result[i].dest+" == " + result[i].weight); 
	} 

	// Driver Program 
	public static void main (String[] args) 
	{ 

		/* Let us create following weighted graph 
				10 
			0--------1 
			| \	 | 
		6| 5\ |15 
			|	 \ | 
			2--------3 
				4	 */
		int V = 4; // Number of vertices in graph 
		int E = 5; // Number of edges in graph 
		Graph graph = new Graph(V, E); 

		// add edge 0-1 
		graph.edge[0].src = 0; 
		graph.edge[0].dest = 1; 
		graph.edge[0].weight = 10; 

		// add edge 0-2 
		graph.edge[1].src = 0; 
		graph.edge[1].dest = 2; 
		graph.edge[1].weight = 6; 

		// add edge 0-3 
		graph.edge[2].src = 0; 
		graph.edge[2].dest = 3; 
		graph.edge[2].weight = 5; 

		// add edge 1-3 
		graph.edge[3].src = 1; 
		graph.edge[3].dest = 3; 
		graph.edge[3].weight = 15; 

		// add edge 2-3 
		graph.edge[4].src = 2; 
		graph.edge[4].dest = 3; 
		graph.edge[4].weight = 4; 

		graph.KruskalMST(); 
	} 
} 
//This code is contributed by Aakash Hasija 
 
by

Java online compiler

Write, Run & Share Java code online using OneCompiler's Java online compiler for free. It's one of the robust, feature-rich online compilers for Java language, running the Java LTS version 17. Getting started with the OneCompiler's Java editor is easy and fast. The editor shows sample boilerplate code when you choose language as Java and start coding.

Taking inputs (stdin)

OneCompiler's Java online editor supports stdin and users can give inputs to the programs using the STDIN textbox under the I/O tab. Using Scanner class in Java program, you can read the inputs. Following is a sample program that shows reading STDIN ( A string in this case ).

import java.util.Scanner;
class Input {
    public static void main(String[] args) {
    	Scanner input = new Scanner(System.in);
    	System.out.println("Enter your name: ");
    	String inp = input.next();
    	System.out.println("Hello, " + inp);
    }
}

Adding dependencies

OneCompiler supports Gradle for dependency management. Users can add dependencies in the build.gradle file and use them in their programs. When you add the dependencies for the first time, the first run might be a little slow as we download the dependencies, but the subsequent runs will be faster. Following sample Gradle configuration shows how to add dependencies

apply plugin:'application'
mainClassName = 'HelloWorld'

run { standardInput = System.in }
sourceSets { main { java { srcDir './' } } }

repositories {
    jcenter()
}

dependencies {
    // add dependencies here as below
    implementation group: 'org.apache.commons', name: 'commons-lang3', version: '3.9'
}

About Java

Java is a very popular general-purpose programming language, it is class-based and object-oriented. Java was developed by James Gosling at Sun Microsystems ( later acquired by Oracle) the initial release of Java was in 1995. Java 17 is the latest long-term supported version (LTS). As of today, Java is the world's number one server programming language with a 12 million developer community, 5 million students studying worldwide and it's #1 choice for the cloud development.

Syntax help

Variables

short x = 999; 			// -32768 to 32767
int   x = 99999; 		// -2147483648 to 2147483647
long  x = 99999999999L; // -9223372036854775808 to 9223372036854775807

float x = 1.2;
double x = 99.99d;

byte x = 99; // -128 to 127
char x = 'A';
boolean x = true;

Loops

1. If Else:

When ever you want to perform a set of operations based on a condition If-Else is used.

if(conditional-expression) {
  // code
} else {
  // code
}

Example:

int i = 10;
if(i % 2 == 0) {
  System.out.println("i is even number");
} else {
  System.out.println("i is odd number");
}

2. Switch:

Switch is an alternative to If-Else-If ladder and to select one among many blocks of code.

switch(<conditional-expression>) {    
case value1:    
 // code    
 break;  // optional  
case value2:    
 // code    
 break;  // optional  
...    
    
default:     
 //code to be executed when all the above cases are not matched;    
} 

3. For:

For loop is used to iterate a set of statements based on a condition. Usually for loop is preferred when number of iterations is known in advance.

for(Initialization; Condition; Increment/decrement){  
    //code  
} 

4. While:

While is also used to iterate a set of statements based on a condition. Usually while is preferred when number of iterations are not known in advance.

while(<condition>){  
 // code 
}  

5. Do-While:

Do-while is also used to iterate a set of statements based on a condition. It is mostly used when you need to execute the statements atleast once.

do {
  // code 
} while (<condition>); 

Classes and Objects

Class is the blueprint of an object, which is also referred as user-defined data type with variables and functions. Object is a basic unit in OOP, and is an instance of the class.

How to create a Class:

class keyword is required to create a class.

Example:

class Mobile {
    public:    // access specifier which specifies that accessibility of class members 
    string name; // string variable (attribute)
    int price; // int variable (attribute)
};

How to create a Object:

Mobile m1 = new Mobile();

How to define methods in a class:

public class Greeting {
    static void hello() {
        System.out.println("Hello.. Happy learning!");
    }

    public static void main(String[] args) {
        hello();
    }
}

Collections

Collection is a group of objects which can be represented as a single unit. Collections are introduced to bring a unified common interface to all the objects.

Collection Framework was introduced since JDK 1.2 which is used to represent and manage Collections and it contains:

  1. Interfaces
  2. Classes
  3. Algorithms

This framework also defines map interfaces and several classes in addition to Collections.

Advantages:

  • High performance
  • Reduces developer's effort
  • Unified architecture which has common methods for all objects.
CollectionDescription
SetSet is a collection of elements which can not contain duplicate values. Set is implemented in HashSets, LinkedHashSets, TreeSet etc
ListList is a ordered collection of elements which can have duplicates. Lists are classified into ArrayList, LinkedList, Vectors
QueueFIFO approach, while instantiating Queue interface you can either choose LinkedList or PriorityQueue.
DequeDeque(Double Ended Queue) is used to add or remove elements from both the ends of the Queue(both head and tail)
MapMap contains key-values pairs which don't have any duplicates. Map is implemented in HashMap, TreeMap etc.