Question

Algorithm implementation in Java please.

Answer 1

Explanation::

Code in JAVA is given below

Union.java and computernetwork.java files are created inside the package named codejudge42

Code in JAVA::

Union.java Code::

package codejudge42;

import java.util.ArrayList;

class Union{

ArrayList<Integer> unionList;

ArrayList<Integer> rootList;

Union(int n) {

unionList = new ArrayList<>();

rootList = new ArrayList<>();

for (int i = 0; i < n; i++){

unionList.add(i);

rootList.add(i, 1);

}

}

public int find(int i){

int rootI = i;

while(rootI != unionList.get(rootI)){

rootI = unionList.get(rootI);

}

while(i != rootI){

int nextRoot = unionList.get(i);

unionList.set(i, rootI);

i=nextRoot;

}

return rootI;

}

public void unionLink(int i, int j){

int i1 = find(i);

int j1 = find(j);

if (i1 == j1){

return;

}

if (rootList.get(i1) < rootList.get(j1)){

rootList.set(j1, rootList.get(j1) + rootList.get(i1));

unionList.set(i1, j1);

}

else{

rootList.set(i1, rootList.get(j1) + rootList.get(i1));

unionList.set(j1, i1);

}

}

public boolean isConnected(int i, int j){

int iID = find(i);

int jID = find(j);

return iID == jID;

}

}

computernetwork.java Code::

package codejudge42;

import java.util.ArrayList;

import java.util.Scanner;

public class computernetwork {

public static void main(String[] args) {

Scanner scan = new Scanner(System.in);

int m = scan.nextInt();

int n = scan.nextInt();

Union pcNet = new Union(m);

for(int counter = 0; counter < n; counter++){

String newline = scan.nextLine();

if (newline.equals("")){newline = scan.nextLine();}

Scanner intScan = new Scanner(newline.substring(1));

int i,j;

char c = newline.charAt(0);

if (c == 'A'){

i = intScan.nextInt();

j = intScan.nextInt();

pcNet.unionLink(i, j);

}

else {

i = intScan.nextInt();

j = intScan.nextInt();

if((pcNet.isConnected(i, j))== true){

System.out.println("YES");

}

else{

System.out.println("NO");

}

}

}

}

}

OUTPUT::

4 5

A 0 1

C 0 3

NO

C 0 1

YES

A 1 3

C 0 3

YES

Please provide the feedback!!

Thank You!!