TLE in FOXLINGS SPOJ Problem Statement: FOXLINGS
  
  It’s Christmas time in the forest, and both the Fox and the Wolf
  families are celebrating. The rather large Fox family consists of two
  parents as well as \$N\$ (\$1 \leq N \leq 10^9\$) little Foxlings. The
  parents have decided to give their children a special treat this year
  – crackers! After all, it’s a well-known fact that Foxen love
  crackers.
  
  With such a big family, the parents can’t afford that many crackers.
  As such, they wish to minimize how many they give out, but still
  insure that each Foxling gets at least a bit. The parents can only
  give out entire crackers, which can then be divided and passed around.
  
  With this many children, not all of them know one another all that
  well. The Foxlings have names, of course, but their parents are
  computer scientists, so they have also conveniently numbered them from
  \$1\$ to \$N\$. There are \$M\$ (\$1 \leq M \leq 10^5\$) unique two-way
  friendships among the Foxlings, where relationship \$i\$ is described by
  the distinct integers \$A_i\$ and \$B_i\$ (\$1 \leq A_i,B_i \leq N\$),
  indicating that Foxling \$A_i\$ is friends with Foxling \$B_i\$, and vice
  versa. When a Foxling is given a cracker, he can use his tail to
  precisely split it into as many pieces as he wants (the tails of Foxen
  have many fascinating uses). He can then pass these pieces around to
  his friends, who can repeat this process themselves.
  
  Input
  
  Line 1: 2 integers, \$N\$ and \$M\$
  
  Next \$M\$ lines: 2 integers, \$A_i\$ and \$B_i\$, for \$i=1\ldots M\$
  
  Output
  
  A single integer – the minimum number crackers must be given out, such
  that each Foxling ends up with at least a small part of a cracker.


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&lt;=n; i++){
            dj[i]= i;
            size[i]= 1;
        }
        HashMap&lt;Integer, Integer&gt; map= new HashMap&lt;&gt;();
        int count=0;
        for(int i=0; i&lt;m; i++){
            int n1= br.nextInt();
            int n2= br.nextInt();
            union(dj, size, n1, n2);
        }

        for(int i=1; i&lt;=n; i++){
            findParent(dj, i);
        }

        for(int i=1; i&lt;=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] &lt; size[posP2]){
                int temp= posP1;
                posP1= posP2;
                posP2= temp;
            }
            arr[posP2]= posP1;
            size[posP1] += size[posP2];
        }
    }



  Note: Reader is just another fast inputting
for(int i=1; i&lt;=n; i++){
    findParent(dj, i);
}

for(int i=1; i&lt;=n; i++){
    if(!map.containsKey(dj[i])){
       count++;
        map.put(dj[i], 1);
    }
}


This part is slow and unnecessary - you can count how many times you did union instead. 

 int[] dj= new int[n+1];


With 10^9 limit for N, only that line requires 4GB of RAM, when limit for task is 1.5GB. Use HashMap instead and store only unioned ids - there will be at most 2*M of those.