Implementation requirements In java. Connectivity must be tested using a tree-ba
ID: 3694069 • Letter: I
Question
Implementation requirements
In java.
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
import java.util.*;
public class Network_Connected {
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
int nodes = scan.nextInt();
//System.out.println(nodes);
int links = scan.nextInt();
//System.out.println(links);
int[][] graph = new int[nodes][nodes];
int[] visit = new int[nodes];
int v1,v2;
for(int i =0;i<nodes;i++)
{
visit[i]=0;
for(int j =0;j<nodes;j++)
{
graph[i][j]=0;
}
}
for(int i=0;i<links;i++)
{
v1 = scan.nextInt();
v2 = scan.nextInt();
//System.out.println(v1);
//System.out.println(v2);
graph[v1][v2]=1;
graph[v2][v1]=1;
}
//System.out.println("******");
//We will do a DFS to check if we can visit all the vertices
Stack st = new Stack();
st.push(0);
int curr;
while(!st.empty())
{
curr = (int)st.pop();
visit[curr]=1;
for(int i=0;i<nodes;i++)
{
if(graph[curr][i]==0)continue;
if(visit[i]==1)continue;
st.push(i);
}
}
int flag=1;
for(int i=0;i<nodes;i++)
{
if(visit[i]==0)
{
flag=0;
break;
}
}
if(flag==0)
System.out.println("Not connected");
else
System.out.println("Connected");
}
}