本文共 8841 字，大约阅读时间需要 29 分钟。

A Bug's Life

23 31 22 31 34 21 23 4

Scenario #1:Suspicious bugs found!Scenario #2:No suspicious bugs found!

首先这道题的想法就是类似于食物链的那道题，我们就是类似于把他们看成两个不同的集合，然后合并相同部分的集合，最后再判断本来应该属于不同种类的他们的祖先是不是同一个了，如果是同一个的话，那么就是错误的了。

#include
   
    int par[4010];int find(int x){	return par[x]==x?x:par[x]=find(par[x]);}void merge(int x,int y){	int tx,ty;	tx=find(x);	ty=find(y);	if(tx!=ty) par[tx]=ty;}int main(){	int T;	int n,m,j=1;	int x,y;	scanf("%d",&T);	for(int i=1;i<=T;i++){		int flag=0;		scanf("%d%d",&n,&m);		for(int i=1;i<=2*n;i++) par[i]=i;		while(m--){			scanf("%d%d",&x,&y);			if(find(x)==find(y)){				flag=1;  			}			else{				merge(x,y+n);				merge(x+n,y);			}		}		printf("Scenario #%d:\n",i);		if(flag) printf("Suspicious bugs found!\n");		else puts("No suspicious bugs found!");		puts("");	}}
   

Virtual Friends

13Fred BarneyBarney BettyBetty Wilma

234

这道题的题目意思大致是：每次给出两个人名，然后每次叫你输出每次刚成为朋友的两个人所形成的朋友圈中一共有几个朋友。

其实，实质就是一道并查集以及要用到map来储存人名，map在这里的作用是为了给每个人来标记序号，从而就不会重复了。

这里注意，map不要忘记清空。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
      
     
    
   

Dragon Balls

Five hundred years later, the number of dragon balls will increase unexpectedly, so it's too difficult for Monkey King(WuKong) to gather all of the dragon balls together. 

His country has N cities and there are exactly N dragon balls in the world. At first, for the ith dragon ball, the sacred dragon will puts it in the ith city. Through long years, some cities' dragon ball(s) would be transported to other cities. To save physical strength WuKong plans to take Flying Nimbus Cloud, a magical flying cloud to gather dragon balls. 

Every time WuKong will collect the information of one dragon ball, he will ask you the information of that ball. You must tell him which city the ball is located and how many dragon balls are there in that city, you also need to tell him how many times the ball has been transported so far.

23 3T 1 2T 3 2Q 23 4T 1 2Q 1T 1 3Q 1

Case 1:2 3 0Case 2:2 2 13 3 2

这道题是我认为现在碰到的一道新的并查集的题目。

题目的大致意思是：一开始n个龙珠都被放在n个城市里。

然后有Q次询问，一种是：“T A B "，代表和A在一起的球全被运到B所在的城市里去了。

Q  A：就代表的是询问，对于每次询问，你要输出A球所在的城市X，以及X中有几个球，以及A球被转运了几次。

对于前两个询问我们是比较容易的处理的。于是我学习了一下怎么求A球被转运了几次。

这里我们用到了路径压缩的知识，其实合并两个集合的次数就是可以看做第一个集合的根节点的移动次数加1，这里我们可以在递归调用的时候改变移动次数。

其实我对这里的改变次数还不是理解的很透彻。

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;#define maxn 11111int par[maxn],num[maxn],tmove[maxn];void init(){	for(int i=1;i<=maxn;i++) par[i]=i;}int find(int x){	if(par[x]==x) return x;		int temp=par[x];		par[x]=find(par[x]);		//这里的目的是为了全部更新子节点的移动次数为根的加1； 		tmove[x]+=tmove[temp];		return par[x];}void merge(int x,int y){	int tx,ty;	tx=find(x);	ty=find(y);	// 注意下面的判断条件，只有当两个是不同时，才是tmove[tx]=1; 因为此时是第一次移动； 	if(tx!=ty){		par[tx]=ty;		tmove[tx]=1;		num[ty]+=num[tx];		num[tx]=0;	}}int main(){	int T,n,q,j=1;	char c[5];	scanf("%d",&T);	while(T--){		bool ff=false;		init();		fill(num,num+maxn,1);		memset(tmove,0,sizeof(tmove));		int a,b;		scanf("%d%d",&n,&q);		while(q--){			scanf("%s",c);			if(c[0]=='T'){				scanf("%d%d",&a,&b);				merge(a,b);			}			else if(c[0]=='Q'){				scanf("%d",&a);				int t=find(a);				if(!ff){					printf("Case %d:\n",j++); ff=true;				}				printf("%d %d %d\n",t,num[t],tmove[a]);			}		}	}}
      
     
    
   

#include 
   
    #include 
    
     #define maxn 10005int transport[maxn];//transport[i]表示i球转移了多少次int ball[maxn];//ball[i]表示i球在哪个城市,其实是并查集中的集合 int city[maxn];//city[i]表示i号城市有几个球 /*带权并查集*/void initialize(){	for(int i = 0 ; i <= maxn - 1 ; ++i)	{		ball[i] = i;//初始i号球在i城市 		city[i] = 1;//初始i城市只有一个球 		transport[i] = 0;//初始i号球没有经过任何转移 	}}int find_root(int x){	    //ball[x]是x的父节点 	if(x == ball[x])		return x;	int temp = ball[x]; 	ball[x] = find_root(ball[x]);	transport[x] += transport[temp];	//注意这条语句和上条顺序不可颠倒，这一过程是在回溯时完成的 	return ball[x];	}void Union(int x,int y){	int root1 = find_root(x);	int root2 = find_root(y);	if(root1 != root2)	{		ball[root1] = root2;		transport[root1] = 1;//第一次移动 		city[root2] += city[root1]; 		city[root1] = 0;//移动完毕后置0 		//这里的city其实是并查集的树的高度。 	}}int main(){	int Case;	int balls,query;	int from,to;	char cmd[5];		scanf("%d",&Case);	int count = 0;	while(Case--)	{		initialize();		printf("Case %d:\n",++count);		scanf("%d%d",&balls,&query);		while(query--)		{			scanf("%s",cmd);			if(cmd[0] == 'Q')			{				int k;				scanf("%d",&k);				int x = find_root(k);				printf("%d %d %d\n",x,city[x],transport[k]);			}			if(cmd[0] == 'T')			{				scanf("%d%d",&from,&to);				Union(from,to);			}		}	}	return 0;}
    
   

转载地址：https://blog.csdn.net/ACMer_hades/article/details/45849099 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！