题意是:有n的操作,arrive str1 m 然后m个数,表示str1到教室,并且他知道m信息,信息的标号为输入的m个数,
share str1 str2 表示str1和str2 两个人交换两个人的信息。并且当第三个人与其中一个人交换信息时,另一个人也交换。即这三个人相互知道他们的信息。
check str1 表示查询 str1这个人知道信息的条数。
题解:并查集。
#include<cstdio> #include<cstring> #include<string> #include<map> #include<set> #include<queue> #include<iostream> using namespace std; #define FreOpen freopen("Input.txt","r",stdin) #define mem(x,y) memset(x,y,sizeof(x)) int pre[100010]; set<int>S[100010]; map<string,int>M; void init(int n) { for(int i=0;i<=n;i++) S[i].clear(),pre[i]=i; M.clear(); } int main() { //FreOpen; int n,i,j; char str1[20],str2[20],str[20]; while(~scanf("%d",&n)) { init(n); int num=0; while(n--) { scanf("%s",str); if(str[0]=='a') { scanf("%s",str1); M[str1]=num;//进行编号.//下行为对应set中的信息. for(scanf("%d",&i);i>0;i--,scanf("%d",&j),S[num].insert(j) ); num++; } else if(str[0]=='s') { scanf("%s%s",str1,str2); i=M[str1];//i的编号 j=M[str2];//j的编号 while(pre[i]!=i) i=pre[i];//找到祖先节点. while(pre[j]!=j) j=pre[j]; if(i==j) continue;//i和j在一个集合中. M[str1]=j;M[str2]=j;//优化。这两人已经交换信息, pre[i]=j;//i指向j。 编号直接指向j。 while(!S[i].empty())//将i集合信息合并到j中。 { int x=*S[i].begin(); S[j].insert(x); S[i].erase(x);//删除该元素. } } else { scanf("%s",str1); i=M[str1];//str1人的编号. while(pre[i]!=i) i=pre[i];//找到祖先. M[str1]=i; printf("%d\n",S[i].size()); } } } return 0; }