时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 32768K，其他语言65536K

64bit IO Format: %lld

题目描述

给你一个 n 个点，m 条边的无向图，求至少要在这个的基础上加多少条无向边使得任意两个点可达~ 

输入描述:

第一行两个正整数 n 和 m 。 接下来的m行中，每行两个正整数 i 、 j ，表示点i与点j之间有一条无向道路。

输出描述:

输出一个整数，表示答案

示例1

输入

4 21 23 4

输出

1

备注:

对于100%的数据，有n,m<=100000。 分析：并查集。

1 #include
        
          2 #include
         
           3  4 int N,M;//N个点M条边  5 int pre[200012];//pre[i]=x表示点i的父亲节点为点x  6 int a[200012]; 7 void init()//初始化N个元素pre[x]=x,即开始时有N个集合  8 { 9     for(int i=0;i<=N;i++) pre[i]=i;10 }11 12 int find(int x)//查询某点所在树的根 13 {14     int root=x;15     while(pre[root]!=root)16     root=pre[root];17     18     int i=x,k;19     while(k!=root)//路径压缩,让x所在树的所有节点直接指向根节点 20     {21         k=pre[i];22         pre[i]=root;23         i=k;24     }25     return root; 26 }27 28 int unite(int x,int y)29 {30     int rootx=find(x),rooty=find(y);31     if(rootx!=rooty)32     {pre[rootx]=pre[rooty];return 1;}33     return 0;34 }35 36 int main()37 {38     scanf("%d",&N);39         scanf("%d",&M);40         init();41         int x,y,ans=N;42         for(int i=1;i<=M;i++)43         {44             scanf("%d%d",&x,&y);45             ans-=unite(x,y);46         }47         printf("%d\n",ans-1);48     return 0;49 }