From the question I attempted with disjoint sets. I applied union by size along with path compression. But the constraints are very high and I could not think how to optimize this further. Offcourse I am getting TLE with solution upon submitting. So can anyone tell me any trick or idea regarding optimization?
public static void main(String[] argh) throws Exception{
// BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Reader br= new Reader();
int n= br.nextInt();
int m= br.nextInt();
int[] dj= new int[n+1];
int[] size= new int[n+1];
for(int i=1; i<=n; i++){
dj[i]= i;
size[i]= 1;
}
HashMap<Integer, Integer> map= new HashMap<>();
int count=0;
for(int i=0; i<m; i++){
int n1= br.nextInt();
int n2= br.nextInt();
union(dj, size, n1, n2);
}
for(int i=1; i<=n; i++){
findParent(dj, i);
}
for(int i=1; i<=n; i++){
if(!map.containsKey(dj[i])){
count++;
map.put(dj[i], 1);
}
}
System.out.println(count);
}
private static int findParent(int[] arr, int pos){
if(arr[pos] == pos) return pos;
return arr[pos]= findParent(arr, arr[pos]);
}
private static void union(int[] arr, int[] size, int pos1, int pos2){
int posP1= findParent(arr, pos1);
int posP2= findParent(arr, pos2);
if(posP1 != posP2){
if(size[posP1] < size[posP2]){
int temp= posP1;
posP1= posP2;
posP2= temp;
}
arr[posP2]= posP1;
size[posP1] += size[posP2];
}
}
Note: Reader is just another fast I/O