Description
Input
Output
Sample Input
10 9 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 10 4 2 3 4 5 4 8 5 8 0 0
Sample Output
Case 1: 1 Case 2: 7
一开始并不是要做这个题的，而是要做食物链那个题，不过实在想不出具体作法，于是就网搜了，某神牛说做那个题要先做这个题，于是就做了，不过这个题的难度跟那个题没法比啊，就是简单的并查集
#include<map> #include<set> #include<queue> #include<cmath> #include<vector> #include<cstdio> #include<string> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 0x0f0f0f0f using namespace std; const double pi=acos(-1.0); const double eps=1e-8; typedef pair<int,int>pii; const int maxn=50001; int p[maxn]; bool vis[50001]; int find(int x) { return x==p[x]?x:p[x]=find(p[x]); } int main() { //freopen("in.txt","r",stdin); int n,m,ans,x,y,k=0; while (scanf("%d%d",&n,&m)!=EOF && !(n==0 && m==0)) { k++; for (int i=1;i<=n;i++) {p[i]=i;vis[i]=false;} while (m--) { scanf("%d%d",&x,&y); x=find(x); y=find(y); p[x]=y; } ans=0; for (int i=1;i<=n;i++) { p[i]=find(i); if (!vis[p[i]]) { ans++; vis[p[i]]=true; } } printf("Case %d: %d\n",k,ans); } //fclose(stdin); return 0; }
poj 2524 Ubiquitous Religions,布布扣,bubuko.com
原文：http://www.cnblogs.com/chensunrise/p/3690089.html