Question
IN JAVA PLEASE
Background
A minimum requirement when building a computer network is to ensure that every computer can communicate with every other computer in the network, possibly via intermediate computers. For this project you must write a program to determine whether or not a proposed set of direct computer-to-computer communication links will result in a connected network. Assuming that communication links are bidirectional, the network can naturally be represented as an undirected graph in which nodes are the computers and edges are the direct communication links between them. A sample network with 7 computers and 8 communication links is shown below:
Implementation requirements
Connectivity must be tested using a tree-based implementation of the partition/union-find data structure with union-by-size and path compression (see Section 14.7.3 of the book).
Program Input
Your program must read the description of the network from the standard input. The description starts with a line containing the number n of nodes and the number m of links in the network, where n and m are non-negative integers. Each of the following m lines contains a pair of integers between 0 and n-1, corresponding to the two ends of a communication link.
Program Output
You must print to the standard output a newline terminated line containing the message "connected" if the input network is connected, and "not connected" if the input network is not connected.
Sample Input 1
An input representing the network in the figure above is:
Output for Sample Input 1
Sample Input 2
Output for Sample Input 2
Explanation / Answer
public class QuickUnionUF { private int[] parent; // parent[i] = parent of i private int count; // number of components /** * Initializes an empty union-find data structure with N sites * 0 through N-1. Each site is initially in its own * component. * * @param N the number of sites * @throws IllegalArgumentException if N < 0 */ public QuickUnionUF(int N) { parent = new int[N]; count = N; for (int i = 0; i = N) { throw new IndexOutOfBoundsException("index " + p + " is not between 0 and " + (N-1)); } } /** * Returns true if the the two sites are in the same component. * * @param p the integer representing one site * @param q the integer representing the other site * @return true if the two sites p and q are in the same component; * false otherwise * @throws IndexOutOfBoundsException unless * both 0 ≤ p < N and 0 ≤ q < N */ public boolean connected(int p, int q) { return find(p) == find(q); } /** * Merges the component containing site p with the * the component containing site q. * * @param p the integer representing one site * @param q the integer representing the other site * @throws IndexOutOfBoundsException unless * both 0 ≤ p < N and 0 ≤ q < N */ public void union(int p, int q) { int rootP = find(p); int rootQ = find(q); if (rootP == rootQ) return; parent[rootP] = rootQ; count--; } /** * Reads in a sequence of pairs of integers (between 0 and N-1) from standard input, * where each integer represents some object; * if the sites are in different components, merge the two components * and print the pair to standard output. */ public static void main(String[] args) { int N = StdIn.readInt(); QuickUnionUF uf = new QuickUnionUF(N); while (!StdIn.isEmpty()) { int p = StdIn.readInt(); int q = StdIn.readInt(); if (uf.connected(p, q)) continue; uf.union(p, q); StdOut.println(p + " " + q); } StdOut.println(uf.count() + " components"); } }