Hello, everyone. I have a problem with the FIRESC. Can you tell me what is wrong with my code? It would be also nice if you can provide some test cases that might be a tricky. Thanks in advance.
import java.util.*;
public class Main {
static int[] employee;
public static void main(String[] args) {
Scanner read = new Scanner(System.in);
int t = read.nextInt();
while(t-- > 0) {
int n = read.nextInt();
int m = read.nextInt();
employee = new int[n];
for(int i=0; i<n; i++) {
employee[i] = i;
}
WeightQuickUnion qUnion = new WeightQuickUnion(employee);
//Relation between employee
for(int i=0; i<m; i++) {
int a = read.nextInt();
int b = read.nextInt();
if(!qUnion.isConnect(a-1, b-1))
qUnion.union(a-1,b-1);
}
qUnion.findRoot();
System.out.println(qUnion.getWay() + " " + qUnion.getLeader());
}
}
}
class WeightQuickUnion {
private int[] id;
private int[] sz;
private List<Integer> root = new ArrayList<Integer>();
public WeightQuickUnion(int[] id) {
this.id = id;
sz = new int[id.length];
for(int i=0; i<id.length; i++) {
id[i]=i;
sz[i]++;
}
}
public int root(int i) {
while(i != id[i]) {
id[i] = id[id[i]];
i = id[i];
}
return i;
}
public void union(int p, int q) {
int i = root(p);
int j = root(q);
if(sz[i] > sz[j]) {
id[j] = i;
sz[i] += sz[j];
}
else {
id[i] = j;
sz[j] += sz[i];
}
}
public boolean isConnect(int p, int q) {
return root(p)==root(q);
}
public long getLeader() {
long temp = 1;
for(int i=0; i<root.size(); i++) {
temp *= sz[root.get(i)];
}
return temp;
}
public void findRoot() {
for(int i=0; i<id.length; i++) {
if(id[i] == i) {
root.add(i);
}
}
}
public int getWay() {
return root.size();
}
}