則最後的集合數量即為結果。求集合數量:判斷有多少個根節點,用到根節點的特征(其父節點為自己)
代碼如下:
#include#include #include using namespace std; int n,m; int f[52014]; void init() { for(int i=1; i<=n; i++) f[i]=i; } int find(int x) { return f[x]==x?x:find(f[x]); } void unity(int a,int b) { if(find(a)!=find(b)) f[find(a)]=find(b); } int main() { int ji=1; while(cin>>n>>m) { if(n+m==0)break; init(); while(m--) { int a,b; cin>>a>>b; unity(a,b); } int ans=0; for(int i=1; i<=n; i++) if(f[i]==i) ans++; cout<<"Case "<