Description
There are so many different religions in the world today that it is difficult to keep track of them all. You are interested in finding out how many different religions students in your university believe in.Input
The input consists of a number of cases. Each case starts with a line specifying the integers n and m. The next m lines each consists of two integers i and j, specifying that students i and j believe in the same religion. The students are numbered 1 to n. The end of input is specified by a line in which n = m = 0.Output
For each test case, print on a single line the case number (starting with 1) followed by the maximum number of different religions that the students in the university believe in.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
Hint
Huge input, scanf is recommended.題意:輸入n,m代表有n個幫派,下面輸入m行x,y,代表學生x,y同一個幫派,問總共有多少個幫派。
思路:典型的並查集。求出每個的集合,數數這些集合的個數即可
#include#include #include #include #include using namespace std; int uset[100010]; int rank[100010]; void makeset(int n) { memset(uset,0,sizeof(uset)); for(int i=1;i<=n;i++) uset[i]=i; } int find(int x) { if(uset[x]!=x) uset[x]=find(uset[x]); return uset[x]; } void unionset(int x,int y) { if((x=find(x))==(y=find(y))) return; if(rank[x]>rank[y]) uset[y]=x; else { uset[x]=y; if(rank[x]==rank[y]) rank[y]++; } } int main() { int n,m,i; int a,b; int t=1; while(~scanf("%d %d",&n,&m)) { if(n==0&&m==0) break; makeset(n); while(m--) { scanf("%d %d",&a,&b); unionset(a,b); } int sum=0; for(i=1;i<=n;i++) { if(uset[i]==i) sum ++; } printf("Case %d: %d\n", t++, sum); } return 0; }