(如果复制到控制台无换行，可以先粘贴到文本编辑器，再复制)
10 91 21 31 41 51 61 71 81 91 1010 42 34 54 85 80 0样例输出
Case 1: 1Case 2: 7提示
数据量巨大，C++程序推荐用 scanf#----------------------------------------------------------------------------------------------#
写这道题并不是想说什么思路，主要是想记录一个惊天地泣鬼神的东西（这一点也不夸张……）
很多时候并查集需要找集合的个数（比如这道题），所以，我们应该怎么办呢？
我的第一次方法是：
找每一个结点的根，用一个bool数组记录，有一个新的就sum++：
for(int i=1;i<=n;i++) if(!ans[father[i]]) { ans[father[i]]=1; sum++; }于是就有了严重的错误（还很耗时……对于这种在其他OJ上5秒限制而这里1秒限制来说就更恶心得要死了）……所以，我发现了一个方法（尽管很容易想到，然而我没有）：
直接数根结点个数！
我一下子就觉悟了……
反正我的根结点标记是-1，就这样即可：
for(int i=1;i<=n;i++) if(father[i]==-1) sum++;我用了路径压缩，所以不用再找root。代码：
#include<cstdio>#include<cstring>int father[50005];int n,m,k;int root(int x){ if(father[x]==-1) return x;//找到根 father[x]=root(father[x]);//找的时候路径压缩，路径压缩是什么？简单说就是使一个集合的除根结点以外所有点的father都变为根结点 return father[x];}int main(){ while(1) { scanf("%d%d",&n,&m); if(!n&&!m) return 0; memset(father,-1,sizeof(father));//默认每个数都是根结点 for(int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); int rx=root(x),ry=root(y); if(rx!=ry)//两个数不在一个集合 father[ry]=rx;//就合并 } int sum=0; for(int i=1;i<=n;i++) if(father[i]==-1) sum++;//刚刚说的方法 PRintf("Case %d: %d/n",++k,sum); }} By WZY#----------------------------------------------------------------------------------------------#
新闻热点
疑难解答
