求助大佬
  • 板块学术版
  • 楼主GXZJQ
  • 当前回复4
  • 已保存回复4
  • 发布时间2024/4/1 21:22
  • 上次更新2024/4/2 11:47:09
查看原帖
求助大佬
1088732
GXZJQ楼主2024/4/1 21:22

我遇到了一个灵异事件

首先,这是一道题,链接如下:

题目链接

这是没有注释掉输出中间变量语句的代码:

#include<iostream>
using namespace std;
const int maxn = 1e5 + 10;
int n, m, p, q, k, op;
int fa[maxn], my_size[maxn], sum[maxn];
//fa[]储存父节点
//my_size[]储存该树的大小
//sum[]储存这棵树的所有元素和
int find(int x) {
	if (fa[x] == x) return x;
	else return fa[x] = find(fa[x]);
	//迭代寻找祖先
}
void merge(int x, int y) {
	int rex = find(x), rey = find(y);
	if (rex == rey) return;
	if (my_size[rex] < my_size[rey]) swap(rex, rey);
	//尽量让小树往大树上合并
	fa[rex] = rey;
	//更改祖先
	my_size[rey] += my_size[rex];
	sum[rey] += sum[rex];
	//更改属性
	my_size[rex] = 0, sum[rex] = 0;
	//清空
	//合并两个集合
}
void move(int x, int y) {
	int rex = find(x), rey = find(y);
	if (rex == rey) return;
	fa[x] = rey;
	//将元素转移
	my_size[rex]--, my_size[rey]++;
	sum[rex] -= x, sum[rey] += x;
	//更新属性
	//将x添加到y所在的集合
}
void init() {
	for (int i = 1; i <= n; i++) {
		fa[i] = i;
		sum[i] = i;
		my_size[i] = 1;
	}
	//初始化
}
int main() {
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	while (cin >> n >> m) {
		init();
		while (m--) {
			cin >> op;
			if (op == 1) {
				cin >> p >> q;
				merge(p, q);
//				cout<<"这里是对merge函数的调试部分: "<<p<<" "<<q<<" "<<my_size[find(p)]<<" "<<my_size[find(q)]<<endl;
			} else if (op == 2) {
				cin >> p >> q;
				move(p, q);
//				cout<<"这里是对move函数的调试部分: "<<p<<" "<<q<<" "<<my_size[find(p)]<<" "<<my_size[find(q)]<<endl;
			} else {
				cin >> k;
				cout << "这里是题目输出部分: "<< my_size[find(k)] << " " << sum[find(k)] << endl;
			}
		}
	}
	return 0;
}

程序输出结果是:

5 7
1 1 2
这里是对merge函数的调试部分: 1 2 2 2
2 3 4
这里是对move函数的调试部分: 3 4 2 2
1 3 5
这里是对merge函数的调试部分: 3 5 3 3
3 4
这里是题目输出部分: 3 12
2 4 1
这里是对move函数的调试部分: 4 1 3 3
3 4
这里是题目输出部分: 3 7
3 3
这里是题目输出部分: 2 8

然后,我注释掉了输出中间变量语句,然后它的输出是这样的:

5 7
1 1 2
2 3 4
1 3 5
3 4
这里是题目输出部分: 3 12
2 4 1
3 4
这里是题目输出部分: 3 7
3 3
这里是题目输出部分: 3 7

所以有没有大佬知道这是为什么啊

2024/4/1 21:22
加载中...