1703.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"stdio.h"
#include"memory.h"
long diff[100010];
long same[100010];
long stack[100010];
void swap(long &a,long &b)
{long c=a;a=b;b=c;}
int main()
{long i,a,b,n,m;
	int tt;
	char c;
	long p,t,num;
	//cin>>tt;
	scanf("%d",&tt);
	while(tt--)
	{//cin>>n>>m;
		scanf("%ld%ld",&n,&m);
	memset(diff,0,(n+1)*sizeof(long));
	memset(same,0,(n+1)*sizeof(long));
	for(i=0;i<m;i++)
	{//cin>>c>>a>>b;
		do
		{
			scanf("%c",&c);
		}while(c!='A'&&c!='D');
		scanf("%ld%ld",&a,&b);

	if(c=='D'){p=diff[a];t=diff[b];
		   
		   num=0;
		   while(same[a]){stack[num++]=a;a=same[a];}
		   for(num--;num>=0;num--)same[stack[num]]=a;
		   num=0;
		   while(same[b]){stack[num++]=b;b=same[b];}
		   for(num--;num>=0;num--)same[stack[num]]=b;
		   
		   if(same[t])
			{num=0;
		         while(same[t]){stack[num++]=t;t=same[t];}
                         for(num--;num>=0;num--)same[stack[num]]=t;
			}
		   if(t!=a&&t)same[a]=t;
							 
		   if(same[p])
		   	{num=0;
		   	while(same[p]){stack[num++]=p;p=same[p];}
		   	for(num--;num>=0;num--)same[stack[num]]=p;
		   	}
		   if(p!=b&&p)same[b]=p;
		   	
		   diff[a]=b;
		   diff[b]=a;
		  }
	if(c=='A'){
		   while(same[a])a=same[a];
		   while(same[b])b=same[b];
		   if(a==b){printf("In the same gang.\n");
			   //cout<<"In the same gang."<<endl;
			   continue;}
		   p=diff[a];t=diff[b];
		   if(p){while(same[p])p=same[p];
		   	if(p==b){printf("In different gangs.\n");
				//cout<<"In different gangs."<<endl;
				continue;}
		   	}
		   if(t){while(same[t])t=same[t];
		        if(t==a){printf("In different gangs.\n");
					//cout<<"In different gangs."<<endl;
				continue;}
			}
		   printf("Not sure yet.\n");
		   //cout<<"Not sure yet."<<endl;
		}

	}
}
return 0;
	}