2019 蓝桥杯省赛 B 组模拟赛（四） 程序设计：队列

题目：


代码如下：
50%数据

#include<bits/stdc++.h>
using namespace std;
#define MAX 50005
vector<int> a[MAX];
int f[MAX];
int father(int x)
{
	while(x != f[x]) x = f[x];
	return x;
}
void combine(int x,int y)
{
	int xx = father(x);
	int yy = father(y);
	if(xx != yy) f[yy] = xx;
}
int main()
{
	char s;
	int n,m,num1,num2;
	cin >> n >> m;
	for(int i = 1;i <= n;i++) a[i].push_back(i);
	for(int i = 1;i <= n;i++) f[i] = i;
	while(m--){
		cin >> s;
		if(s == 'T'){
			cin >> num1 >> num2;
			if(father(num1) == father(num2)) continue;
			else{
				int xx = father(num1);
				int yy = father(num2);
				combine(num1,num2);
				for(int i = 0;i < a[yy].size();i++) a[xx].push_back(a[yy][i]);
				a[yy].clear();
			}
		}
		else if(s == 'Q'){
			bool flag = false;
			int sum2 = 0;
			cin >> num1;
			int xx = father(num1);
			for(int i = 0;i < a[xx].size();i++){
				if(flag) sum2++;
				if(a[xx][i] == num1) flag = true;
			}
			cout << sum2 << endl;
		}
	} 
	return 0;
}

100%数据：

#include<bits/stdc++.h>
using namespace std;
#define MAX 50005
int f[MAX],ans[MAX],num[MAX]; //ans[i]统计i集团人数，num[i]表示i后面排多少人 
int find_father(int x)
{
	if(x == f[x]) return x;
	int temp = f[x];
	f[x] = find_father(f[x]);
	ans[x] += ans[temp];
	return f[x];
}
void init(int n)
{
	for(int i = 1;i <= n;i++){
		f[i] = i;
		num[i] = 1;
		ans[i] = 0;
	}
}
void combine(int x,int y)
{
	int xx = find_father(x);
	int yy = find_father(y);
	if(xx != yy){
		f[xx] = yy;//y集合排到x最后，就把y当父结点 
		ans[xx] = num[yy];//x后面排的人数就是y集团的人数 
		num[yy] += num[xx]; 
	}	
} 
int main()
{
	int n,m,x,y;
	char s;
	while(scanf("%d%d",&n,&m) == 2){
		init(n);
		while(m--){
			scanf(" %c",&s);
			if(s == 'T'){
				scanf("%d%d",&x,&y);
				combine(x,y);
			}
			else if(s == 'Q'){
				scanf("%d",&x);
				find_father(x);
				printf("%d\n",ans[x]);
			}
		}
	} 
	return 0;
}