題目描述

輸入

輸出

樣例輸入

Copy (如果復制到控制臺無換行，可以先粘貼到文本編輯器，再復制)

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
#----------------------------------------------------------------------------------------------#