链接
一些话
伞兵人做伞兵事，题目用0作为多组输入的结尾，写题的时候我用while(~scanf("%d",&n))，结果死活不认结尾0，（最气人的是我看的一篇题解也是这样写的）然后去查了while(~scanf("%d",&n))的用法：
while(~scanf("%d", &n)) 等价于 while(scanf("%d",&n)!=EOF)
此题要用while(scanf("%d",&n) && n)
套路：
1、多组输入
1、多组输入
（1）条件：多组数据，以EOF作为结尾或无特殊结尾
对策：while(~scanf("%d", &n)）注意：题目以-1为结尾时，要用套路三而不是这个套路
（2）条件：多组数据，以0作为结尾
对策：while(scanf("%d", &n) && n)
（3）条件：多组数据，以k作为结尾
对策：while(scanf("%d",&n) && n != k)
2、并查集合并：
条件：需要合并两个并查集
void un(int x,int y){ int fx = find(x); int fy = find(y); if(fx != fy){ f[fx] = fy; } }
3、并查集查找：
条件：普通的并查集根节点查找，没有特殊功能
int find(int x){ while(f[x] != x) x = f[x]; return x; }
4、并查集数量：
条件：求并查集的存在数量、检查点位连通情况
(1)数据给n个点位，从1-n编号
int cnt = 0; for(int i = 1;i <= n;i++){ if(f[i] == i) cnt++; } if(cnt == 1)//全部点位连通
(2)不给点位数，只给范围：
要配合记录点位存在情况的数组:
int cnt = 0; for(int i = 1;i < N:i++){ if(ap[i] && f[i] == i)cnt++; } if(cnt == 1)//全部点位连通
暂时是这么多，路径压缩这题没用到，虽然总结了但是不在这写
最后是ac代码
#include <iostream> using namespace std; const int N = 1e3 + 10; int f[N],cnt[N]; int find(int x){ while(f[x] != x){ x = f[x]; } return f[x]; } void un(int x,int y){ int fx = find(x); int fy = find(y); if(fx != fy){ f[fx] = fy; } } int main(){ int n,m; while(scanf("%d",&n) && n){ scanf("%d",&m); for(int i = 1;i <= n;i++){ f[i] = i; cnt[i] = 1; } while(m--){ int x,y; scanf("%d%d",&x,&y); un(x,y); } int res = 0; for(int i = 1;i <= n;i++){ if(f[i] == i) res++; } printf("%d\n",res - 1); } return 0; }
