CONGRAPH  Connected country
After a strong earthquake many roads of the ancient country GRAPH were destroyed. The country is divided into disconnected areas so that from one area city it is impossible to reach another area city. Pharaoh wants to restore the road infrastructure and connect all the cities. He asks the great Thoth to find the minimum number of roads needed for this.
Input
The first line of input will contain two space separated integer numbers: 0 < N ≤ 800000, number of cities and 0 < M < 4000000, number of roads. Follow M lines. Each line represents cities (numbering is zero based) connected by road. All roads are bidirectional.
Output
One integer number. Answer of the Thoth
Example
Input: 6 6 0 1 0 2 1 2 3 4 3 5 4 5
Output: 1
Example explanation
One road from the city number 1 to the city number 4 makes GRAPH connected.
hide comments
paritosh99:
20201117 04:22:17
AC in one go....No need to do the union, just find the no. of disconnected components ans will be one less than that.e.g. in given example, two diconnected components are there so only one road needed. 

blaize11:
20201105 09:26:57
connected components1 

shikhar_may7:
20200503 23:35:00
In the case of DSU, Balance the tree when taking Union else it will result in TLE! 

y17prashant:
20191101 03:28:52
DSU is working fine 

medhruv7:
20190829 08:11:09
My Dsu not working here , got AC with dfs , plz help 

samael42:
20190605 12:07:47
#connected components 1 
Added by:  julkas 
Date:  20180521 
Time limit:  10s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 