Program IN JAVA

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:

7 8 0 1 0 2 1 3 2 3 2 4 3 5 3 6 5 6 

Output for Sample Input 1

connected 

Sample Input 2

10 9 0 1 1 2 1 7 3 9 4 7 4 8 5 7 6 9 7 8 

Output for Sample Input 2

not connected