1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 #define MAX 100001 6 using namespace std; 7  8 int Computer; 9 typedef struct node{10     int data_;//节点对应人的编号11     int rank_;//节点对应的秩12     int parent_;//节点对应双亲下标13 }UFSTree;14 void MAKE_SET(UFSTree t[]);//初始化并查集树15 int FIND_SET(UFSTree t[],int x);//在x所在子树中查找集合编号16 void UNION(UFSTree t[],int x,int y);//将x和y所在的子树合并17 int main()18 {19     #ifndef ONLINE_JUDGE20         freopen("D:\\acm.txt","r",stdin);21     #endif // ONLINE_JUDGE22     int success,unsuccess;23     char testCase[100];//数组要开的大一些，否则会re24     int caseNum;25     cin>>caseNum;26     while(caseNum--){27         cin>>Computer;28         success = unsuccess = 0;29         UFSTree t[MAX];30         MAKE_SET(t);31         getchar();32         while(gets(testCase)){33             if(testCase[0] == 0)break;34             int x,y;35             sscanf(testCase + 1, "%d%d",&x,&y);//要用输入流，用数组提取会wa36             int xx = FIND_SET(t,x),yy = FIND_SET(t,y);37             if(testCase[0] == ‘c‘){38                 if(xx != yy )UNION(t,x,y);39             }40             if(testCase[0] == ‘q‘){41                 if(xx != yy)unsuccess ++;42                 else success ++;43             }44         }45         cout<<success<<","<<unsuccess<<endl;46         if(caseNum)cout<<endl;47     }48     return 0;49 }50 void MAKE_SET(UFSTree t[]){51     for(int i = 1;i <= Computer;i++){52         t[i].data_ = i;//数据为该人编号53         t[i].rank_ = 1;//秩，即节点的个数54         t[i].parent_ = i;//父节点指向自己55     }56 }57 int FIND_SET(UFSTree t[],int x){58     if(x != t[x].parent_){59         return (FIND_SET(t,t[x].parent_));60     }61     else62         return x;63 }64 void UNION(UFSTree t[],int x,int y){65     x = FIND_SET(t,x);66     y = FIND_SET(t,y);67     if(x==y)return;68     if(t[x].rank_ > t[y].rank_){69             t[y].parent_ = x;70             t[x].rank_ += t[y].rank_;71     }72     else{73         t[x].parent_ = y;74         t[y].rank_ += t[x].rank_;75     }76 }