1 #include <cstdio> 2 #include<iostream> 3 #define MAX 30 4 using namespace std; 5  6 int CharNum; 7 typedef struct node{ 8     int data_;//节点对应人的编号 9     int rank_;//节点对应的秩10     int parent_;//节点对应双亲下标11 }UFSTree;12 void MAKE_SET(UFSTree t[]);//初始化并查集树13 int FIND_SET(UFSTree t[],int x);//在x所在子树中查找集合编号14 void UNION(UFSTree t[],int x,int y);//将x和y所在的子树合并15 int main()16 {17 18     //freopen("D:\\acm.txt","r",stdin);19     int caseNum;20     char MaxChar[20],pairChars[20];21     scanf("%d",&caseNum);22     getchar();getchar();23     while(caseNum--){24         gets(MaxChar);25         CharNum = MaxChar[0] - ‘A‘ + 1;//字母的个数26         int flag = 0;//子图的个数27         UFSTree t[MAX];28         MAKE_SET(t);29         while(gets(pairChars)){30             int x,y;31             if(pairChars[0] == 0)break;32             x = pairChars[0] - ‘A‘ + 1;33             y = pairChars[1] - ‘A‘ + 1;34             if(FIND_SET(t,x)!= FIND_SET(t,y)){35                 UNION(t,x,y);36             }37         }38         for(int i = 1;i <= CharNum;i++){//统计子图的个数39             if(t[i].parent_ == i)flag++;40         }41         printf("%d\n",flag);42         if(caseNum)printf("\n");//两个输出样例之间有一空行，因为这WA了好多次43     }44     return 0;45 }46 void MAKE_SET(UFSTree t[]){47     for(int i = 0;i <= CharNum;i++){//要从0开始，否则会RE，实际0不使用。48         t[i].data_ = i;//数据为该人编号49         t[i].rank_ = 1;50         t[i].parent_ = i;//父节点指向自己51     }52 }53 int FIND_SET(UFSTree t[],int x){//找到祖宗节点54     if(x != t[x].parent_){55         return (FIND_SET(t,t[x].parent_));56     }57     else58         return x;59 }60 void UNION(UFSTree t[],int x,int y){61     x = FIND_SET(t,x);62     y = FIND_SET(t,y);63     if(x == y)return;64     if(t[x].rank_ > t[y].rank_){65             t[y].parent_ = x;66             t[x].rank_ += t[y].rank_;//更新连接的个数67     }68     else{69         t[x].parent_ = y;70         t[y].rank_ += t[x].rank_;//更新连接的个数71     }72 }