PLEASE PROGRAM IN JAVA THIS PROGRAM Connectivity must be tested using a tree-bas

Question

PLEASE PROGRAM IN JAVA
THIS PROGRAM Connectivity must be tested using a tree-based implementation of the partition/union-find data structure with union-by-size and path compression.

MUST INCLUDE Partition/union-find data structure with union-by-size and path compression.

PLEASE INCLUDE

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

package pathcompression;

import java.util.Scanner;

public class QuickUnionPathCompressionUF {
private int[] id; // id[i] = parent of i
private int count; // number of components

/**
* Initializes an empty union-find data structure with N isolated components 0 through N-1.
* @param N the number of sites
* @throws java.lang.IllegalArgumentException if N < 0
*/
public QuickUnionPathCompressionUF(int N) {
count = N;
id = new int[N];
for (int i = 0; i < N; i++) {
id[i] = i;
}
}

/**
* Returns the number of components.
*
* @return the number of components (between <tt>1</tt> and <tt>N</tt>)
*/
public int count() {
return count;
}
  
/**
* Returns the component identifier for the component containing site <tt>p</tt>.
*
* @param p the integer representing one object
* @return the component identifier for the component containing site <tt>p</tt>
* @throws IndexOutOfBoundsException unless <tt>0 &le; p &lt; N</tt>
*/
public int find(int p) {
int root = p;
while (root != id[root])
root = id[root];
while (p != root) {
int newp = id[p];
id[p] = root;
p = newp;
}
return root;
}

/**
* 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 <tt>true</tt> if the two sites <tt>p</tt> and <tt>q</tt> are in the same component;
* <tt>false</tt> otherwise
* @throws IndexOutOfBoundsException unless
* both <tt>0 &le; p &lt; N</tt> and <tt>0 &le; q &lt; N</tt>
*/
public boolean connected(int p, int q) {
return find(p) == find(q);
}

/**
* Merges the component containing site <tt>p</tt> with the
* the component containing site <tt>q</tt>.
*
* @param p the integer representing one site
* @param q the integer representing the other site
* @throws IndexOutOfBoundsException unless
* both <tt>0 &le; p &lt; N</tt> and <tt>0 &le; q &lt; N</tt>
*/
public void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) return;
id[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) {
Scanner sc=new Scanner(System.in);
int N = sc.nextInt();
//int N = stdIn.readInt();
QuickUnionPathCompressionUF uf = new QuickUnionPathCompressionUF(N);
while (N > 0) {
int p = sc.nextInt();
int q = sc.nextInt();
if (uf.connected(p, q)) continue;
uf.union(p, q);
System.out.println(p + " " + q);
}
System.out.println(uf.count() + " components");
}

}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

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